Integer Overflow Prevention in C-CodePudding

I am fresh out of CS50x's C section, and I wanted to try to implement the Fibonacci sequence in C. I realised after I ran my program, that integers were overflowing, and using an unsigned long long only gets me to F47. Is there any way to avoid overflows? I could re-implement in python, but my computer is a potato, and I would rather have the fast run speed of C.

Here is my code.

CodePudding user response：

I had such a problem in one of my codes in C. I had to take 60 digits and by using long long int, i had owerflow problems. my problem finished with using char and asci codes instaed of int . I will show you a example for adding a great int to my previous result. my int is greater than long long int: char c; scanf("%c",&c); result=result (c - '0'); this will support more digits and i think your code in this way will do better.

CodePudding user response：

Your code is almost correct, you should use fprintf(out, "%lli\n", j); instead of %i as j has type long long. This explains why your implementation fails after F47.

long long has 63 value bits, enough for F92 = 7540113804746346429.

Using unsigned long long should get you one extra result: F93 = 12200160415121876738.

Testing for overflow in your case is easy as both i and j are positive:

#include <limits.h>
#include <stdio.h>

void fibonacci(long long N, FILE *out)
{
    fprintf(out, "0\n1\n");

    if (N > 2)
    {
        for (long long z = 0, i = 0, j = 1, next = 0; z < N - 2; z  )
        {
            if (i > LLONG_MAX - j) {
                fprintf(out, "Overflow\n");
                break;
            }
            //Next is i   j
            next = i   j;
            //old j becomes the new i
            i = j;
            //old next becomes the new j
            j = next;
            //Print j (the old next)
            fprintf(out, "%lli\n", j);
        }
    }
}

If you want to compute larger Fibonacci numbers, you must use bignums. There is no standard support for bignums in the C library, but multiple implementations are available in open source.

Here is a simplistic approach using strings for large numbers:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *bignum_add(char *a, char *b) {
    size_t a_len = strlen(a), b_len = strlen(b);
    if (a_len < b_len) {
        char *c = a; a = b; b = c;
        size_t x = a_len; a_len = b_len; b_len = x;
    }
    size_t i, c_len = a_len   1;
    char *c = malloc(c_len   1);
    if (c == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    c[0] = '0';
    memcpy(c   1, a, a_len   1);
    for (i = 1; i <= b_len; i  ) {
        if ((c[c_len - i]  = b[b_len - i] - '0') > '9') {
            c[c_len - i] -= 10;
            c[c_len - i - 1]  ;
        }
    }
    for (; c[c_len - i] > '9'; i  ) {
        c[c_len - i] -= 10;
        c[c_len - i - 1]  ;
    }
    if (c[0] == '0' && c_len > 1) {
        memmove(c, c   1, c_len--);
    }
    return c;
}

char *fib(int n) {
    char *current = strdup("0");
    if (n > 0) {
        char *prev = current;
        current = strdup("1");
        for (int i = 1; i < n; i  ) {
            printf("fib(%d) = %s\n", i, current);
            char *next = bignum_add(prev, current);
            free(prev);
            prev = current;
            current = next;
        }
        free(prev);
    }
    return current;
}

int main(int argc, char *argv[]) {
    int n = (argc > 1) ? strtol(argv[1], NULL, 0) : 100;
    char *f = fib(n);
    printf("fib(%d) = %s\n", n, f);
    free(f);
    return 0;
}