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

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

感谢 Eric Postpischil，请注意， Fibonacci_Invert通常不是用于查找最大Fibonacci数不大于其自变量的正确函数。
您可以 run the code for method 2 online看到以下输出:

IndexMax: 46
FibonacciMax: 1836311903
calculation time: 23 microseconds