CODEWITHSUNDEEP
coverflowlong-integerunsignedaddition
Matt Gilene
Matt Gilene

Reputation: 39

Checking for unsigned long long overflow

I am trying to generate fibonacci numbers and I am storing them as unsigned long longs. However i wish to stop generating more numbers if the new number in the series is larger than what a unsigned long long can hold. I currently have the following.

unsigned long long n1 = 1, n2 = 1, n3;
    int i;
    for(i = 0; i < n; i++) {
        if(i == 0 || i == 1) {
            fprintf(fibonacci_file, "%lld\n", n1);
        }else {
            n3 = n1 + n2;
            if(n3 < n1) {
                printf("FIBONACCI OVERFLOW\n");
                break;
            }else {
                fprintf(fibonacci_file, "%lld\n", n3);
                n1 = n2;
                n2 = n3;
            }
        }
    }

Then end of the output file looks like this.

1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
-6246583658587674878

The last one is negative, meaning the result overflowed. However my check should have caught it and not printed it out, and ended the loop.

Upvotes: 0

Views: 1082

Answers (1)

chux
chux

Reputation: 154176

Wrong specifier used to print the full range of unsigned long long. Use "%llu". @void_ptr

unsigned long long n3;
....
// fprintf(fibonacci_file, "%lld\n", n3);
fprintf(fibonacci_file, "%llu\n", n3);

OP's method of detecting overflow is fine as in C, mathematical overflow is well defined to simply "wrap". That is pseudo-code: unsigned_sum = math_sum mod (UMAX+1) given the max of the type involved.

 if (n3 < n1) {
   printf("FIBONACCI OVERFLOW\n");
   break;

A deleted discussion also proposed an idiomatic test @Weather Vane and @Olaf which would also work. This approach is useful when the type involved is not unsigned integers, but signed integers or floating point.

 if (ULLONG_MAX - n2 < n1) {
   printf("FIBONACCI OVERFLOW\n");
   break;
 }
 n3 = n1 + n2;

Further, the series is sometimes considered to start at F[0] = 0. See Fibonacci number

Upvotes: 3

Related Questions