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

Question

下面的代码能够使用数据类型确定直到70点的正确顺序unsigned long long.我知道序列会变大,因此我修改了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的正确结果.

为了加快算法速度,您可以使用快速加倍的Fibonacci:

   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