优化代码：斐波那契算法

我正在研究一个真正的大数字（第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; 
}

来源

2015-10-16 Pikson

这个问题属于矩阵为[codereview.se] –

使用功率。 – MikeCAT

@ sam2090这是DP方法 –

无论您在给定的代码上执行了多么优秀的优化，也无需更改基础算法，只能对其进行微小优化。你的方法具有线性复杂性，对于大值它会很快变慢。更快的实现斐波那契数是通过对矩阵做矩阵exponentiation by squaring：

0 1 
1 1

这种做法将与对数的复杂性是渐近更好。执行这个矩阵的几个指数，你会注意到n + 1 st斐波那契数在它的右下角。

来源

2015-10-16 13:25:47

+1没有通过OP的代码读取。通常'fibonacci'是'递归的'所以我认为这可能也是:)。可能[this]（http://fusharblog.com/solving-linear-recurrence-for-programming-contest/）可能有用 – sam

有一些方法渐近地与q-matrix方法相同，但在实践中速度更快，例如[http://dx.doi.org/10.1016/S0020-0190(80)90076-9]。阅读引用本文的论文来寻找其他高级算法可能会有帮助。这是我的这个算法的实现[https://github.com/yuhanlyu/Snippets/blob/master/experiments/fibonacci/fib.c]。 –

我会节省一些预先计算的点（特别是因为你正在寻找真正的大数字）

即说我救了第500次和第501号FIB。那么如果有人问我什么是600纤维？我会从502开始计算，而不是从1开始计算。这真的会节省时间。

现在问题你会保存多少点，以及如何选择要保存的点？

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

来源

2015-10-16 13:25:37 knightrider

我建议你为你的大数字使用类似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

来源

2015-10-16 13:53:06 pokey909

优化代码：斐波那契算法

回答

相关问题