C语言实现斐波那契数列如何避免整数溢出问题

你想要保留C语言性能优势同时解决溢出问题，核心是使用大整数运算，不需要切换到Python，C的实现效率依然远高于Python，完全适配低配置设备。

首先先指出你最初版本代码的两个问题：

1. 格式符不匹配：你定义的j是long long类型，但fprintf用了%i（对应int类型），就算没有溢出，输出大于int范围的数值也会出错，需要改成%lld才能正确输出long long类型的值。
2. 原生整数长度限制：即使用unsigned long long，最大只能存到2^64-1，对应斐波那契数列最多到第93项，你遇到的只能算到第47项是因为signed int的上限就是2^31-1，要突破这个限制必须用大整数方案。

接下来分两种可行方案：

方案1：手动实现大整数加法（你当前思路的优化版） #

你现在用char类型做加法的思路是完全可行的，属于手动实现大整数的入门方案，可以继续优化提升性能：

• 存储优化：不要直接存ASCII字符，数组每个位置存0~9的数字值，输出时再加'0'转成字符，省去运算过程中字符转数字的开销
• 存储顺序优化：按低位在前的规则存储（数组下标0存个位，下标1存十位，以此类推），加法进位时不需要整体移动数组，运算效率更高
• 内存优化：可以通过黄金分割比提前预估斐波那契数的位数，提前分配内存，避免频繁动态扩容的开销

简化的手动大整数实现示例：

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

// 按低位在前存储大整数，len是当前位数
typedef struct {
    uint8_t *digits;
    size_t len;
    size_t capacity;
} BigInt;

// 大整数加法：a + b = res
void bigint_add(const BigInt *a, const BigInt *b, BigInt *res) {
    size_t max_len = a->len > b->len ? a->len : b->len;
    // 确保res容量足够，多留一位存进位
    if (res->capacity < max_len + 1) {
        res->digits = realloc(res->digits, max_len + 1);
        res->capacity = max_len + 1;
    }
    uint8_t carry = 0;
    size_t i;
    for (i = 0; i < max_len; i++) {
        uint8_t sum = carry;
        if (i < a->len) sum += a->digits[i];
        if (i < b->len) sum += b->digits[i];
        res->digits[i] = sum % 10;
        carry = sum / 10;
    }
    if (carry) {
        res->digits[i] = carry;
        res->len = max_len + 1;
    } else {
        res->len = max_len;
    }
}

// 输出大整数
void bigint_print(const BigInt *num, FILE *out) {
    for (int i = num->len - 1; i >= 0; i--) {
        fprintf(out, "%c", num->digits[i] + '0');
    }
    fputc('\n', out);
}

方案2：使用成熟的GMP大整数库 #

如果不想自己手写大整数逻辑，直接用GMP（GNU多精度算术库）即可，它是专门优化的大整数运算库，性能比普通手写的大整数实现高很多，完全保留C的运行速度优势，实现逻辑非常简单：

#include <gmp.h>
#include <stdio.h>

void fibonacci(unsigned long long N, FILE *out) {
    if (N >= 1) fprintf(out, "0\n");
    if (N >= 2) fprintf(out, "1\n");
    if (N <= 2) return;

    mpz_t a, b, next;
    mpz_init_set_ui(a, 0);
    mpz_init_set_ui(b, 1);
    mpz_init(next);

    for (unsigned long long z = 2; z < N; z++) {
        mpz_add(next, a, b);
        mpz_out_str(out, 10, next);
        fputc('\n', out);
        mpz_swap(a, b);
        mpz_swap(b, next);
    }

    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(next);
}

编译时加上-lgmp参数链接GMP库即可。

内容的提问来源于stack exchange，提问作者RP-Lens