c - C 中具有大数字(即 1000 位)的斐波那契函数

Question

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

我在 while 循环的末尾添加了addition(): if(进位) f3[i] = 进位;

感谢 FalconUSA 和 M_Oehm ! :)

我正在研究欧拉计划的第 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 。您可能还想检查斐波那契部分:https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html .

更新您可能还想查看这篇文章，其中演示了如何从头开始实现快速斐波那契:https://www.anfractuosity.com/2012/10/24/fib-calculation-with-gmp .

使用 GMP 的优点是，您将拥有非常快速且复杂的算法，这些算法是由知道自己做什么的人编写的。 GMP速度极快(部分用汇编语言编写，深度利用了各种算法)，库成熟稳定。每当您需要处理大量数据时，使用 GMP 总是一个好主意。