フィボナッチ数の大きい数字の検索

Question

大きなフィボナッチ数のモジュラスを見つけるための次のプログラムを書いた。これは大きな数値を解決できますが、fibo_dynamic(509618737,4602,229176339)のような場合は計算できません。a = 509618737、b = 4602、N = 229176339です。この仕事をするのを手伝ってください。

long long fibo_dynamic(long long x,long long y,long long n, long long a[]){ 
    if(a[n]!=-1){ 
     return a[n]; 
    }else{ 
     if(n==0){ 
      a[n]=x; 
      return x; 
     }else if(n==1){ 
      a[n]=y; 
      return y; 
     }else { 
      a[n]=fibo_dynamic(x,y,n-1,a)+fibo_dynamic(x,y,n-2,a); 
      return a[n]; 
     } 
    } 
} 

Answer 1

フィボナッチ数が急激に増加するため、値がオーバーフローします。元のフィボナッチシリーズ（f(0) = 0およびf(1) = 1）の場合でも、f(90)の値は20桁を超えており、C++のプリミティブデータ型には格納できません。 （あなたはあなたの質問でそれを言及したので）あなたは、おそらくこのような範囲内の値を保持するためにモジュラス演算子を使用する必要があります。

a[n] = (fibo_dynamic(x,y,n-1,a) + fibo_dynamic(x,y,n-2,a)) % MOD; 

modオペレータは、以下のルールを持っているので、それはすべての段階で値modに安全である：

if a = b + c, then: 
a % n = ((b % n) + (c % n)) % n 

また、再帰バージョンを使用してフィボナッチ数を計算しています（小さな問題の結果をメモしていますが）。これは、余分なオーバーヘッドを追加する再帰呼び出しがたくさんあることを意味します。可能であれば、反復バージョンを使用する方がよいでしょう。

次に、変数nでインデックスを作成しています。だから、私は配列aのサイズはatleast nであると仮定しています。質問に記載されているnの値は非常に大きいです。このような大きなサイズの配列をローカルマシンで宣言することはできません（整数のサイズは4 bytes、配列のサイズはa、およそ874 MB）。

最後に、プログラムの複雑さはO(n)です。 O(log(n))時間にn番目のフィボナッチ数を計算する方法があります。 「行列累乗を使って漸化関係を解く」技術を理解するために読むthis

f(n) = f(n-1) + f(n-2) for n >= 2 

：フィボナッチ数は、次の線形漸化式に従ってください。