Integer Overflow Prevention in C

Question

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.

Edit: Here is the original version of my code:

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++)
        {
            //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, "%i\n", j);
        }
    }
}

The link now shows my latest version which works as intended thanks to using chars instead of ints for addition.

By "avoid overflow", do you mean give you an error and halt if something overflows, or magically implement multiprecision arithmetic that doesn't overflow? — Steve Summit, Nov 26 '21 at 20:43
If you want your code to halt on integer overflow, see https://stackoverflow.com/questions/199333 or https://stackoverflow.com/questions/69104632 — Steve Summit, Nov 26 '21 at 20:45
If you want to use bignums, you'll have to either implement them yourself, or use something like [GMP](https://gmplib.org/). — Steve Summit, Nov 26 '21 at 20:46
By avoid overflow, I mean I want to use bigger numbers. I will try GMP. — RP-Lens, Nov 26 '21 at 20:48
Sounds like you're not using `unsigned long long` correctly, though. 64 bits should get you to the 93rd Fibonacci number or so. — Steve Summit, Nov 26 '21 at 20:48
It's easy enough to do a digit-by-digit, right to left, sum with carry as in elementary school if you want really really big numbers (if you want to try this consider using the reversed number for more "easiness"). — pmg, Nov 26 '21 at 20:55
"there any way to avoid overflows?" Use `double` (and tolerate the inexactness of FP math) or use a some type of [far more precision](https://stackoverflow.com/questions/34353558/print-fibo-big-numbers-in-c-or-c-language/34360258#34360258). — chux - Reinstate Monica, Nov 26 '21 at 22:04
question must be self-contained. You must post a [mcve] in the question itself, not in external link which can rot at anytime, rendering the question invalid — phuclv, Nov 27 '21 at 01:28
@RP-Lens We prefer code we can see right here in the question. We prefer not to have to chase links to see your code. Why did you make an edit to take your code back out of the question? It was better with the code in the question. — Steve Summit, Nov 27 '21 at 16:47
@SteveSummit I took the code out of the question because it was an older version with some errors that I fixed. However, I understand your point and I will re-upload it — RP-Lens, Nov 28 '21 at 19:24

score 0 · Answer 1 · answered Nov 26 '21 at 21:45

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.

chqrlie · Accepted Answer · 2021-11-27T10:16:57.143

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

Integer Overflow Prevention in C

2 Answers2