C中的整数溢出预防

Question

我刚从 CS50x 的 C 部分毕业，我想尝试在 C 中实现斐波那契数列。我在运行我的程序后意识到整数溢出，并使用 unsigned long long只能让我到 F47。有什么办法可以避免溢出吗？我可以在 python 中重新实现，但我的计算机是一个土豆，我宁愿拥有 C 的快速运行速度。

这是我的 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);
        }
    }
}

link 现在显示我的最新版本，由于使用字符而不是整数进行加法，它可以按预期工作。

Answer 1

我在 C 中的一个代码中遇到了这样的问题。我必须使用 60 位数字，并且通过使用 long long int，我遇到了 owerflow 问题。我的问题是使用 int 的 char 和 asci 代码完成的。我将向您展示一个将 great int 添加到我之前的结果中的示例。我的 int 大于 long long int： char c; scanf("%c",&c); result=result + (c - '0'); 这将支持更多数字，我认为您的代码以这种方式会做得更好。

Answer 2

您的代码几乎是正确的，您应该使用 fprintf(out, "%lli\n", j); 而不是 %i，因为 j 的类型为 long long。这解释了为什么您的实施在 F47 后失败。

long long 有 63 个值位，足够 F92 = 7540113804746346429.

使用 unsigned long long 应该会得到一个额外的结果：F93 = 12200160415121876738.

在您的案例中测试溢出很容易，因为 i 和 j 都是正值：

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

如果你想计算更大的斐波那契数，你必须使用大数。 C 库中没有对 bignums 的标准支持，但开源中有多种实现。

这是一个使用字符串表示大数字的简单方法：

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

C中的整数溢出预防

Integer Overflow Prevention in C

c

integer

integer-overflow

fibonacci