找到适合整数的最大斐波那契数的最快方法是什么？

Question

我承认这个问题有点学术性。但是，我认为该解决方案在（C ++）数值方面显示出一些见识。

请注意，第N个斐波那契数可以使用递归计算

int Fibonacci(int N)
{
    if (N==1 || N==2) {
        return 1;
    }
    return Fibonacci(N-1) + Fibonacci(N-2);
}

对于这个问题，上述蛮力方法不是答案。这是因为第N个斐波那契数可以通过以下方式非递归计算：

long int Fibonacci(int N)
{
    double num1 = pow((1+sqrt(5))/2.0,N);
    double num2 = pow((1-sqrt(5))/2.0,N);

    return (num1-num2)/sqrt(5);
}

Answer 1

方法1（不是最快的方法：）：>

使用非递归方法来计算第N个斐波那契数您可以使用以下代码找到适合int的最大斐波那契数：

#include <iostream>
#include <limits.h>
#include <math.h>
#include <chrono>

long int Fibonacci(int n)
{
    double num1 = pow((1+sqrt(5))/2.0,n);
    double num2 = pow((1-sqrt(5))/2.0,n);

    return (num1-num2)/sqrt(5);
}

int main()
{
    auto start = std::chrono::system_clock::now();

    int IndexMax = 1;
    while (Fibonacci(IndexMax)<INT_MAX) 
    {
        ++IndexMax;
    }
    --IndexMax;
    auto end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "IndexMax = " << IndexMax << std::endl;
    std::cout << "Fibonacci_two(IndexMax): " << Fibonacci(IndexMax) << std::endl;
    std::cout << "calculation time: " << elapsed.count() << " microseconds" << std::endl;
}
您可以run the code for method 1 online查看以下输出：

IndexMax = 46
Fibonacci_two(IndexMax): 1836311903
calculation time: 33 microseconds
但是还有一个更快的方法：

方法2：

根据Wikipedia，可以将第N个斐波那契数的明确公式取反。使用此技巧，我们可以实现更快的方法：

#include <iostream>
#include <limits.h>
#include <math.h>
#include <chrono>

long int Fibonacci(int n)
{
    double num1 = pow((1+sqrt(5))/2.0,n);
    double num2 = pow((1-sqrt(5))/2.0,n);

    return (num1-num2)/sqrt(5);
}

double Fibonacci_invert(double Fn)
{
    double num1 = Fn*sqrt(5.0);
    double num2 = sqrt(5.0*Fn*Fn+4.0);
    double phi = (1.0 + sqrt(5.0))/2.0;

    return round(log((num1+num2)/2.0)/log(phi));
}

int main()
{
    auto start = std::chrono::system_clock::now();

    int IndexMax = Fibonacci_invert(INT_MAX);
    int FibonacciMax = Fibonacci(IndexMax);

    auto end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "IndexMax: " << IndexMax << std::endl;
    std::cout << "FibonacciMax: " << FibonacciMax << std::endl;
    std::cout << "calculation time: " << elapsed.count() << " microseconds" << std::endl;
}
您可以run the code for method 2 online查看以下输出：

IndexMax: 46
FibonacciMax: 1836311903
calculation time: 23 microseconds

Answer 2

我复制了您的第一个示例，并使用了我使用了很多次的函数。它使用数据代替指令，并使用简单的查找代替计算。它具有斐波那契值的硬编码表，该表适合64位整数。当然，如果只需要32位值，则可以使表变小。