c++ - 我想使用大整数值确定序列中的第 n 个 Fibonacci 项

Question

下面的代码能够使用数据类型 unsigned long long 确定直到 70 的正确序列。我知道序列会变大，因此我修改了 10,000 个结果。我想使用最佳数据类型确定 10,000 的第 n 项或改进算法以计算第 n 项。

#define MOD %10000

unsigned long long calc(long nth) {
    return (pow( 1 + sqrt(5), nth ) - pow( 1 - sqrt(5), nth )) / (pow(2.0, nth)*(sqrt(5)));
}

int main() {
    long t, nth;
    for (std::cin>>t;  t-- && std::cin>>nth; ) {
        std::cout<<calc(nth-2)MOD<<" "<<calc(nth-1)MOD<<" "<<calc(nth)MOD<<std::endl;
    }   
    return 0;
}

Answer 1

由于 sqrn(5) 的浮点错误，您的算法不会计算出大 N 的正确结果。

为了加快您的算法，您可以使用快速加倍斐波那契数列:

   F(2k) = F(k)[2F(k+1) - F(k)]
   F(2k+1) = F(k+1)^2 + F(k)^2

应用模运算，您最终最快的算法将是:

   F(2k) = F(k)[2F(k+1) - F(k)] % 10000
   F(2k+1) = (F(k+1)^2 + F(k)^2) % 10000

使用这种方法，您的函数永远不会超过 10000，因此 int 类型就足够了。

编辑:好的，我在周五晚上有一些空闲时间(我猜这不是一件好事)并实现了算法。我实现了两个版本，第一个版本具有 O(1) 内存和 O(lg n) 时间复杂度，第二个版本使用缓存，内存和最坏情况运行时间为 O(lg n)，但最佳情况运行时间为 O(1)。

#include <iostream>
#include <unordered_map>

using namespace std;

const int P = 10000;

/* Fast Fibonacci with O(1) memory and O(lg n) time complexity. No cache. */

int fib_uncached (int n)
{
    /* find MSB position */
    int msb_position = 31;
    while (!((1 << (msb_position-1) & n)) && msb_position >= 0)
        msb_position--;

    int a=0, b=1; 

    for (int i=msb_position; i>=0;i--)
    {       
        int d = (a%P) * ((b%P)*2 - (a%P) + P),
            e = (a%P) * (a%P) + (b%P)*(b%P);
        a=d%P;
        b=e%P;

        if (((n >> i) & 1) != 0)
        {
            int c = (a + b) % P;
            a = b;
            b = c;
        }
    }
    return a;
}  

/* Fast Fibonacci using cache */
int fib (int n)
{
    static std::unordered_map<int,int> cache;

    if (cache.find(n) == cache.end()) 
    {
        int f;
        if (n==0)
            f = 0;
        else if (n < 3)
            f = 1;
        else if (n % 2 == 0)
        {
            int k = n/2;
            f = (fib(k) * (2*fib(k+1) - fib(k))) % P;
        } 
        else
        {
            int k = (n-1)/2;
            f = (fib(k+1)*fib(k+1)+ fib(k) * fib(k)) % P;
        }
        if (f<0)
            f += P;

        cache[n] = f;
    }
    return cache.at(n);
}

int main ()
{
    int i ;
    cin >> i;
    cout << i << " : " << fib(i) << endl;
return 0;
}

无缓存实现引用:https://www.nayuki.io/page/fast-fibonacci-algorithms