我想使用大的整数值来确定序列中的第n个斐波那契项 [英] I want to determine the nth Fibonacci term in the sequence using large integer values

问题描述

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

The code below is able to determine the correct sequence up to a point namely 70 using the data type unsigned long long. I know the sequence can become large thus I mod 10,000 the results. I want to determine the nth term for 10,000 using the best data type or improve the algo to calculate the nth term.

#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;
}

推荐答案

正确的结果为大的N，由于sqrn（5）的浮点错误。

Your algorithm will not compute the correct result for large N's, due to the floating point errors of sqrn(5).

为了加快算法速度，您可以使用快速倍增的斐波纳契：

In order to speed up your algorithm you can use fast doubling Fibonacci:

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

应用模算术，最终最快的算法为：

Applying modulo arithmetics, your final fastest algorithm would be:

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

方法，你的函数永远不会超过10000，因此 int 类型就足够了。

Using this approach, your function never exceeds 10000, thus an int type suffices.

编辑：在星期五晚上（不是一件好事我猜）和实现的算法。我实现了两个版本，第一个使用 O （1）内存和 O （lg n ）时间复杂度，第二个使用缓存， （1）的最佳情况下的运行时间。

Okay I had some free time on a Friday night (not a good thing I guess) and implemented the algorithm. I implemented two versions, first one with O(1) memory and O(lg n) time complexity and second one using a cache, with memory and worst-case runtime of O(lg n), but with a best case runtime of 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

这篇关于我想使用大的整数值来确定序列中的第n个斐波那契项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！