モジュロmの巨大なフィボナッチ数

Question

Fn mod mを計算しようとしています。ここで、Fnはn番目のフィボナッチ数です。 nは本当に巨大なので、Fnを直接計算するのは実際に効率的ではありません（行列の指数計算はとなります）。 （A + B）モッズメートル= [MOD M + Bのmod M]のmodメートル

（誰もが尋ねる前に：問題文は、剰余の分配プロパティを使用して、Fnキーを計算するせずにこのを行うには、私たちに求められ私はこの同じ問題に対する答えを探しましたが、アルゴリズムこの問題を解決するために質問していないので、私は具体的な質問に答えたいと思います。 n番目のフィボナッチ数は前の2つの和にすぎません。フィボナッチ数を格納する必要はなく、逐次モジュロ演算を計算した結果だけです。その意味では、上記のプロパティを使ってFn mod mを繰り返し計算した結果を格納しているサイズnの配列Fを持つ必要があります。私はこの問題を次のコードを使って解決することができました。しかし、それを見直すと、私はむしろ私を混乱させる何かに遭遇しました。

long long get_fibonacci_huge_mod(long long n, long long m) { 

    long long Fib[3] = {0, 1, 1}; 
    long long result; 
    long long index; 
    long long period; 
    long long F[n+1]; 
    F[0] = 0; 
    F[1] = 1; 
    F[2] = 1; 

    for (long long i = 3; i <= n; i++) { 
     F[i] = (F[i-2] + F[i-1]) % m; 
     if (F[i] == 0 && F[i+1] == 1 && F[i+2] == 1) { 
     period = i; 
     break; 
     } 
    } 


    index = n % period; 
    result = F[index]; 
    return result; 

} 

このソリューションは、nとmがかなり大きい場合でも、正しい結果を出力します。 nが巨大なときには少し遅くなるかもしれませんが、今は心配していません。私はこのように問題を具体的に解決することに興味があります。行列の指数関数または他のはるかに高速なアルゴリズムを使用して解決しようとします後で。

私の質問は次のとおりです。コードの始めに、サイズn + 1の配列Fを作成します。次に、分散配列を使ってFn mod mを計算するこの配列を通して繰り返します。このループを書いた後に私を混乱させたことの1つは、Fがすべて0に初期化されたので、F [i + 2]、F [i + 1]を正しく使用する方法がまだ計算されていない場合です？アルゴリズムの出力がのときに正しくという結果が得られるので、正しく使用されているものとします。おそらく、この仮定は間違っていますか？

私の質問はアルゴリズムそのものについてではなく、私は何が起こっているのかについて質問していますの中にループがあります。ループ。

ありがとうございました

Answer 1

これは正しいアルゴリズムの実装に問題があります。修正されたバージョンを最初に見てみましょう。

long long get_fibonacci_huge_mod(long long n, long long m) { 
    long long result; 
    long long index; 
    long long period = n+1; 
    long long sz = min (n+1,m*m+1); // Bound for period 
    long long *F = new long long[sz]; 
    F[0] = 0; 
    F[1] = 1; 
    F[2] = 1; 

    for (long long i = 3; i < sz; i++) { 
     F[i] = (F[i-2] + F[i-1]) % m; 
     if (F[i] == 1 && F[i-1] == 0) { // we have got back to where we started 
     period = i-1; 
     break; 
     } 
    } 

    index = n % period; 
    result = F[index]; 
    delete[]F; 
    return result; 

} 

元のコードはなぜ機能しますか？あなたは幸運だったから。 i + 1とi + 2のチェックは、配列が初期化されたラッキーなガーベッジのために、真と評価されることはありませんでした。その結果、これは、周期性を全く取り入れずにF（n）の素朴な評価に減少した。