C 中具有大数字（即 1000 位）的斐波那契函数

Question

编辑：我更换：进位 = (x-(x%10))%10; 经过：进位 = x/10;

然后我在 addition() 的 while 循环末尾添加：如果（进位）f3[i] = 进位；

感谢 FalconUSA 和 M_Oehm！ :)

我正在研究 Project Euler 的问题 25（小心剧透），虽然斐波那契函数不是真正的问题，但我很难实现一种存储大量数字的方法（比如 1000 位数字） .

所以我已经尝试（正如我在网上了解到的那样）用数组来处理它，但程序是运行无限期。我的问题可能在 addition() 或 length().

有什么想法吗？

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

int length(int *nbr) // number of digits of my number
{
    int len = 0, c = 0;

    while(nbr[c] >= 0) {
        len++;
        c++;
    }
    return len;
}

int addition(int *f1, int *f2, int *f3, int siz) // add f1+f2 and store it in f3
{
    int carry =0, i =0;
    int x;

    memset ( f3, -1, siz*sizeof(int));

    while ( (f1[i] >= 0) || (f2[i] >= 0) ) {
        if(f1[i]<0) {
            x = f2[i] + carry;
        }
        else if(f2[i]<0) {
            x = f1[i] + carry;
        }
        else {
            x = f1[i] + f2[i] + carry;
        }
        f3[i] = x%10;
        carry = (x-(x%10))%10;
        i++;
    }

    return 0;
}

int copy_arr(int *dest, int *or, int siz) //copy array "or" into "dest"
{
    int c = 0;
    memset( dest, -1, siz*sizeof(int));

    while( c < siz ) {
        dest[c] = or[c];
        c++;
    }

    return 0;
}

int fibo(int siz) //fibonacci function
{
    int f1[siz],f2[siz],f3[siz];
    memset( f1, -1, siz*sizeof(int));
    memset( f2, -1, siz*sizeof(int));
    memset( f3, -1, siz*sizeof(int));

    int n = 2;

    f1[0] = f2[0] = 1;


    while (length(f1) <= siz) {
        n++;
        addition( f1, f2, f3, siz);
        copy_arr( f2, f1, siz);
        copy_arr( f1, f3, siz);
    }

    printf("%d\n", n);

    return 0;
}


int main() // siz's value is the number of digits I desire for my fibonacci number
{
    int siz=1000;

    fibo(siz);

    return 0;
}

Answer 1

您可以使用 GMP 多精度库：https://gmplib.org. You may also want to check Fibonacci section: https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html。

更新您可能还想查看此 post，它演示了如何从头开始实施快速斐波那契数列：https://www.anfractuosity.com/2012/10/24/fib-calculation-with-gmp.

使用 GMP 的优点是您将拥有一个非常快速和精细的算法，由知道他们做什么的人编写。 GMP 速度极快（部分用汇编语言编写，深度利用了各种算法），成熟稳定的库。每当您需要处理大数字时，使用 GMP 总是一个好主意。

Answer 2

嗯，看来你的问题出在这一行：

carry = (x - x%10) % 10;

应该只是

carry = x - x%10;

或

carry = x / 10;

在这种情况下是等价的。

更新： 同样，在

行

 while ( (f1[i] >= 0) || (f2[i] >= 0) ) {

如果f1的大小是siz并且f2的大小也是siz，那么你会到达元素f1[siz]，甚至更远，超出范围。所以，你应该声明

int f1[siz+1], f2[siz+1], f3[siz+1]

你应该在所有地方设置 siz+1 边：

memset( fi, -1, (siz+1)*sizeof(int)); // where 1 <= i <= 3

PS: 如果你只想计算那个斐波那契数而不想集成到一些需要快速计算的程序中，最好使用 Python 或Java，因为这些语言内置了长数字支持，语法也很简单，类似于C++。而且，正如上面提到的 ghostmansd，如果你打算使用 C/C++，最好使用 GMP library。

Answer 3

你的代码有几个问题。

您的号码以标记值为 −1 的数字结尾。您需要 space 作为额外数字，就像您需要 space 作为 C 字符串中的空终止符一样。您应该将数组的维度设置为 siz + 1 并初始化所有值，包括虚拟值。

当您将两个数字相加时，您永远不会考虑最后一个进位。这意味着您的号码永远不会变长。在 addition:

中的主循环之后添加这个

if (carry) f3[i] = carry;

你确定进位的方法也不正确。进位是左边多余的数字：

carry = x / 10;

C 中具有大数字（即 1000 位）的斐波那契函数

Fibonacci function with big number (i.e. 1000 digits) in C

c

bignum

感谢 FalconUSA 和 M_Oehm！ :)