Using float to check overflow in unsigned long int

Question

Hello, all right? Please review this code:

#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;
}

The value defined as max is the largest possible value to store in the unsigned long int type. What happens is that it is quietly stored in a float. The idea is to test multiplication and if it gives greater than the max constant the program should return -1.

However, it seems that there is something wrong when this value is passed to the printipal function via the pointer.

Could someone help me, please?

EDIT: I leave the main implementation below

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;
}

Answer 1

The float has a maximum accuracy of 23 bits, as demonstrated in this answer. Like the unsigned long int must have 32 bits, the float will not be able to store 4294967295 accurately enough. See this:

#include <stdio.h>

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

That’s the way out:

4294967296.000000

See this in ideone.

So you can use two outputs:

• Use double. This will give you 52 bits of accuracy. But if you want to switch to unsigned long long int which has 64 bits (or even for __uint128), will continue with the same problem.

• Check whether n is greater than 1431655764 and burst the overflow if it is (can put a if at the very beginning of the function to do this). How did I arrive at 1431655764? Simple:

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

The number 4294967295 is easier to be expressed in hexadecimal: 0xFFFFFFFF. The max_collatz there is 0x55555554, that is, one unit less than one third of the maximum.

The approach of verifying whether 3 * n + 1 < n does not work for numbers between 2147483648 and 2863311530 (in hexadecimal it is 0x80000000 and 0xAAAAAAAA, that is half and two thirds of the maximum value). Therefore, this is not a good approach to take.

EDIT:

I re-edited your function collatz and took that test:

#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;
}

The output was the whole series of the number 1161 with 181 steps. The largest number found was 190996. See here working on ideone.

I tried with your original code:

#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;
}

The output was also the entire series of the number 1161 with 181 steps and the largest number found was also 190996. See here working on ideone.

Answer 2

You don’t have the code you use to call this function from the outside there - but just passing a pointer to a type float for it to work.

The problem there, for large numbers is that as many as possible in an unsigned long int (2 ** 32 - 1) is not "is quietly stored in a float". A long int has 32 bit, a float has 32 bit in total, but uses 8 bits to store the exponent - do you realize that you have less information in accuracy? What happens is that floating point numbers, like float, double, and long double, have a range greater magnitude, but much less accuracy - they use only 23 bits to store the accuracy of the number itself, and 8 bits to indicate the exponent in base 2 of the number. So the largest number that the float can contain without losing accuracy is 2 ** 23: 8388608 (8 million...), compared to 2*32 -1 : 4294967295 (4 billion)... that you used is the largest unsigned int of 32 bits -if using unsigned long int can have numbers up to 2 ** 64 -1: 18446744073709551615 without losing precision)

So, but for numbers greater than 2** 23 the float type simply discards the information of the least significant digits - and the collatz algorithm has no chance of working, since it precisely depends on the exact integers.

Simply use long integers there, make the comparison with the maximum value before multiply the number by 3, and everything should work.

that is:

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

if (overflow > max_3) return -1;