优化代码：斐波那契算法

Question

我正在为非常大的数字（第 100k 个数字）开发斐波那契算法。不过，我需要使这个运行更快，但仅仅几秒钟，我就运行失去了想法。有什么办法让它更快吗？感谢您的帮助。

#include <iostream>

using namespace std;
int main() {


    string elem_major = "1";
    string elem_minor = "0";
    short elem_maj_int;
    short elem_min_int;
    short sum;
    int length = 1;
    int ten = 0;

    int n;
    cin >> n;


    for (int i = 1; i < n; i++)
    {

        for (int j = 0; j < length; j++)
        {
            elem_maj_int = short(elem_major[j] - 48);
            elem_min_int = short(elem_minor[j] - 48);
            sum = elem_maj_int + elem_min_int + ten;
            ten = 0;
            if (sum > 9)
            {
                sum -= 10;
                ten = 1;
                if (elem_major[j + 1] == NULL)
                {
                    elem_major += "0";
                    elem_minor += "0";
                    length++;
                }
            }
            elem_major[j] = char(sum + 48);
            elem_minor[j] = char(elem_maj_int + 48);
        }
    }

    for (int i = length-1; i >= 0; i--)
    {
        cout << elem_major[i];
    }

    return 0;
}

Answer 1

我会保存一些预先计算的点（特别是因为你正在寻找非常大的数字）

即说我保存了第 500 和 501 个小号。那么如果有人问我第 600 个谎言是什么？我会从 502 而不是从 1 开始计算。这真的会节省时间。

现在的问题是您将节省多少点数以及如何 select 节省点数？

这个问题的答案完全取决于应用程序和可能的分布。

Answer 2

无论您对给定代码执行的优化有多好，如果不更改底层算法，您只能对其进行边际优化。您的方法具有线性复杂性，对于大值，它会很快变慢。斐波那契数列的更快实现是在矩阵上做矩阵 exponentiation by squaring:

0 1
1 1

这种方法将具有对数复杂度，渐近更好。对该矩阵进行几次取幂，您会注意到第 n + 1 个斐波那契数位于其右下角。

Answer 3

我建议您对大数字使用类似 cpp-bigint (http://sourceforge.net/projects/cpp-bigint/) 的东西。代码看起来像这样

#include <iostream>
#include "bigint.h"

using namespace std;
int main() {
    BigInt::Rossi num1(0);
    BigInt::Rossi num2(1);
    BigInt::Rossi num_next(1);

    int n = 100000;

    for (int i = 0; i < n - 1; ++i)
    {
        num_next = num1 + num2;
        num1 = std::move(num2);
        num2 = std::move(num_next);
    }
    cout << num_next.toStrDec() << endl;
    return 0;
}

我机器上的快速基准测试：

time ./yourFib
real    0m8.310s
user    0m8.301s
sys 0m0.005s

time ./cppBigIntFib
real    0m2.004s
user    0m1.993s
sys 0m0.006s

优化代码：斐波那契算法

optimizing code: fibonacci algorithm

c++

algorithm

fibonacci