優化代碼：斐波那契算法

我正在研究一個真正的大數字（第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

優化代碼：斐波那契算法

回答

相關問題