2

Olá, tudo bem? Por favor, analisem esse código:

#define max 4294967295
unsigned long int collatz(unsigned long int n, unsigned long int passos, float *maiorN) {
    float overflow = 3 * n + 1;

    if (n == 1)
        return passos;
    else if (n % 2 == 0)
        return collatz(n / 2, passos + 1, maiorN);
    else if ((overflow) < max) {
        if (overflow > *maiorN)
            *maiorN = overflow;
        return collatz(overflow, passos + 1, maiorN);
    }
    else
        return -1;
}

O valor definido como max é o maior valor possível de se armazenar no tipo unsigned long int. Acontece é que ele é tranquilamente armazenado em um float. A ideia é testar a multiplicação e se ela der maior que a constante max o programa deve retornar -1.

Porém, parece que há algo de errado quando esse valor é passado para a função printipal através do ponteiro.

Alguém poderia me ajudar, por favor?

EDIT: Deixo abaixo a implementação da main

int main(int numargs, char *args[]) {
    unsigned long int passos, n, maiorP, total, N, media;
    FILE *arquivo;
    int inicio, fim;
    float maiorN;

    inicio = N = atoi(args[1]);
    fim = atoi(args[2]); 

    passos = total = maiorP = 0;
    maiorN = 1;
    arquivo = fopen("Log.txt", "w+");

    printf("Teste   Num passos\n");
    fprintf(arquivo, "Teste   Num passos\n");

    for (n = inicio; n <= fim; n++) {
        passos = collatz(n, passos, &maiorN);

        if (passos > maiorP) {
            N = n;
            maiorP = passos;
        }
        if (passos == -1)
            break;


        total += passos;

        fprintf(arquivo, "%lu %10lu\n", n, passos);
        printf("%lu %10lu\n", n, passos);
        passos = 0;
    }    

    media = total/(fim - inicio);

    printf("\nForam testados %d numeros\n", fim - inicio + 1);
    printf("\nDentre os valores testados o num %lu levou %lu passos para convergir para 1 e atingiu o valor maximo de %.0f", N, maiorP, maiorN);
    printf("\nA media de passos para chegar em 1 foi de %lu passos\n", media);

    fprintf(arquivo, "\nForam testados %d numeros\n", fim - inicio + 1);
    fprintf(arquivo, "\n\nDentre os valores testados o num %lu levou %lu passos para convergir para 1 e atingiu o valor maximo de %.0f", N, maiorP, maiorN);
    fprintf(arquivo, "\nA media de passos para chegar em 1 foi de %lu passos", media);



    fclose(arquivo);
    return 0;
}
2

2 Respostas 2

1

O float tem precisão máxima de 23 bits, tal como demonstro nesta resposta. Como o unsigned long int deve ter 32 bits, o float não vai conseguir armazenar 4294967295 com precisão suficiente. Veja isso:

#include <stdio.h>

int main(void) {
    float f = 4294967295;
    printf("%f", f);
}

A saída é essa:

4294967296.000000

Veja isso no ideone.

Então você pode usar duas saídas:

  • Usar double. Isso vai te dar 52 bits de precisão. Mas se você quiser trocar para unsigned long long int que tem 64 bits (ou mesmo para __uint128), vai continuar com o mesmo problema.

  • Verificar se n é maior que 1431655764 e estourar o overflow se for (pode colocar um if logo no começo da função para fazer isso). Como eu cheguei em 1431655764? Simples:

    #define max_collatz ((max - 1) / 3)
    

O número 4294967295 é mais fácil de ser expresso em hexadecimal: 0xFFFFFFFF. O max_collatz aí é 0x55555554, ou seja, uma unidade a menos que um terço do valor máximo.

A abordagem de verificar se 3 * n + 1 < n não funciona para números entre 2147483648 e 2863311530 (em hexadecimal isso é 0x80000000 e 0xAAAAAAAA, ou seja metade e dois terços do valor máximo). Logo, essa não é uma boa abordagem a se tomar.

EDIT:

Reeditei a sua função collatz e fiz esse teste:

#include <stdio.h>

#define max 0xFFFFFFFF
#define max_collatz ((max - 1) / 3)

unsigned long int collatz(unsigned long int n, unsigned long int passos, unsigned long int *maiorN) {
    printf("Passo %lu: %lu\n", passos, n);
    if (n == 1) return passos;
    if (n % 2 == 0) return collatz(n / 2, passos + 1, maiorN);
    if (n > max_collatz) return -1;
    int p = 3 * n + 1;
    if (p > *maiorN) *maiorN = p;
    return collatz(p, passos + 1, maiorN);
}

int main(void) {
    unsigned long int maior = 0;
    collatz(1161, 0, &maior);
    printf("Maior: %lu\n", maior);
    return 0;
}

A saída foi toda a série do número 1161 com 181 passos. O maior número encontrado foi 190996. Veja aqui funcionando no ideone.

Tentei com o seu código original:

#include <stdio.h>

#define max 4294967295
unsigned long int collatz(unsigned long int n, unsigned long int passos, float *maiorN) {
    printf("Passo %lu: %lu. Maior = %f\n", passos, n, *maiorN);
    float overflow = 3 * n + 1;

    if (n == 1)
        return passos;
    else if (n % 2 == 0)
        return collatz(n / 2, passos + 1, maiorN);
    else if ((overflow) < max) {
        if (overflow > *maiorN)
            *maiorN = overflow;
        return collatz(overflow, passos + 1, maiorN);
    }
    else
        return -1;
}

int main(void) {
    float maior = 0;
    collatz(1161, 0, &maior);
    printf("Maior: %d\n", (int) maior);
    return 0;
}

A saída também foi toda a série do número 1161 com 181 passos e o maior número encontrado também foi 190996. Veja aqui funcionando no ideone.

5
  • Eu tinha usado (3*n+1) < max e (3*n + 1) > n para detectar um overflow. Porque, aparentemente, se der overflow o valor será menor do que o n. Será que isso está certo? Pelo menos eu estava conseguindo os mesmos valores. 24/08/2018 às 20:32
  • @LucasLopes Isso não funciona para os números entre 2147483648 e 2863311530. 24/08/2018 às 20:49
  • Segundo esse site www.dcode.fr/collatz-conjecture, o número 1161 leva 181 passos para convergir para 1, o seu maior alcançado é 190996. O meu código calcula o número de passos certo, porém ele diz que o maior número alcançado é 250504. Ambos valores estão longe dos limites de float e unsigned long int. Isso me faz desconfiar que deve estar havendo algum overflow em algum dos passos, mas com esses números baixos não deveria acontecer. Esse programa usa um intervalo de numeros passados como argumentos da linha de comando. Por exemplo: ./collatz 1 1161 calcula os passos do número 1 ao 1161 24/08/2018 às 20:57
  • @LucasLopes Editei a resposta. 24/08/2018 às 21:13
  • 1
    @LucasLopes Descobri o que acontece. O número 703 produz 250504 como maior número em 170 passos. O número 1161 produz 190996 como o maior número em 181 passos. O seu código está certo, você apenas errou em interpretar o resultado ao achar que o mesmo número que gera o maior produzido também é o que gera o maior número de passos, o que não é verdade. 24/08/2018 às 21:27
0

Você não tem o código que usa pra chamar essa função de fora aí - mas bastando passar um ponteiro pra um tipo float pra que ela funcione.

O problema aí, pra números grandes é que o maior número possível num unsigned long int (2 ** 32 - 1) não é "é tranquilamente armazenado em um float". Um long int tem 32 bit, um float tem 32bit no total, mas usa 8 bits pra guardar o expoente - percebe que tem menos informação na precisão? O que acontece é que números em ponto flutuante, como float, double, e long double, tem um alcance maior de grandeza, mas uma precisão muito menor - eles usam apenas 23 bits para armazenar a precisão do número em si, e 8 bits para indicar o expoente na base 2 do número. Então o maior número que o float pode conter, sem perder precisão é 2 ** 23: 8388608 (8 milhões...), comparado com 2**32 -1 : 4294967295 (4 bilhões)... que você usou é o maior unsigned int de 32 bits -se usar unsigned long long int pode ter números até 2 ** 64 -1 : 18446744073709551615 sem perder precisão)

Então, mas para números maiores que 2** 23 o tipo float simplesmente descarta a informação dos dígitos menos significativos - e o algoritmo de collatz não tem a menor chance de funcionar, já que justamente depende dos números inteiros exatos.

Simplesmente use long integers aí, faça a comparação com o valor máximo antes de multiplicar o número por 3, e deve funcionar tudo.

isso é:

#define max 18446744073709551615
#define max_3 max/3
...

if (overflow > max_3) return -1;
4
  • A informação que eu tenho e que retirei desse site pt.wikibooks.org/wiki/Programar_em_C/Tipos_de_dados é que unsigned long int armazena de 0 a 2**32 - 1, ou seja 4294967295. 24/08/2018 às 20:38
  • isso - estava ajustanto a resposta - o unsinged long long int é que tem 64 bits
    – jsbueno
    24/08/2018 às 20:39
  • Tentei mas obtive exatamente o mesmo resultado de antes. 24/08/2018 às 20:47
  • O que você tentou? Minha sugestão final é não usar float, e usar a comparação antes da multiplicação para detectar overflow.
    – jsbueno
    24/08/2018 às 23:00

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .