非常に大きなフィボナッチ数の出力を保存するには？

Question

n番目のフィボナッチ数のプログラムを作っています。私は再帰とメモを使って以下のプログラムを作った。 主な問題は、nの値が10000まで上がる可能性があるということです。つまり、10000のフィボナッチ数が2000桁を超えることになります。

私はちょっと調べてみると、配列を使用して配列の要素にソリューションのすべての数字を格納できることがわかりましたが、私のプログラムでこのアプローチを実装する方法はまだ分かりません。

#include<iostream> 

using namespace std; 

long long int memo[101000]; 
long long int n; 
long long int fib(long long int n) 
{ 
    if(n==1 || n==2) 
     return 1; 
    if(memo[n]!=0) 
     return memo[n]; 
    return memo[n] = fib(n-1) + fib(n-2); 
} 
int main() 
{ 
    cin>>n; 
    long long int ans = fib(n); 
    cout<<ans; 
} 

このアプローチを実装するにはどうすればよいですか、またはそのような大きな値を達成するために使用できる別の方法があるかどうかを確認してください。私が指摘されるべきだと思う

Answer 1

ことの一つは、

を計算するためのC++のようなもののためにはるかに簡単ですfibはこれにはない以下の擬似コード

function fib (n) { 
    let a = 0, b = 1, _; 
    while (n > 0) { 
    _ = a; 
    a = b; 
    b = b + _; 
    n = n - 1; 
    } 
    return a; 
} 

を検討し実施するための他の方法がありますされますメモを必要とするため、再帰呼び出しが多すぎるスタックを吹き飛ばす心配はありません。再帰は本当に強力なループ構造ですが、Lisp、Scheme、Kotlin、Lua（といくつかの他の言語）のようなlangに残しておくと、優雅にサポートすることができます。

これは、C++ではテールコールの除去が不可能だとは限りませんが、明示的に最適化/コンパイルする必要がある場合を除き、使用しているコンパイラによってデフォルトでサポートされるかどうかは疑問です。

非常に大きな数値を計算するには、Hard Wayを追加するか、GMPのような任意精度の算術ライブラリを使用する必要があります。私は確かにこれのための他のライブラリもあります。

ハード・ウェイを追加

---

™

はあなたがアルミ箔オフ新鮮な、少しtater totをした際に大きな数字を追加するために使用する方法を覚えていますか？

5歳の数学

1259601512351095520986368 
+ 50695640938240596831104 
--------------------------- 
          ? 

さてあなたは、右から左へ、各列を追加しなきゃ。列が2桁の数字にオーバーフローした場合は、その1を次の列に持ち越してください。

    ... <-001 
    1259601512351095520986368 
+ 50695640938240596831104 
--------------------------- 
        ... <-472

10,000のフィボナッチ数は、桁数千もの長いので、C++は、箱から出して提供する任意の整数に収まるように起こっている方法はありません。したがって、ライブラリに依存することなく、文字列または1桁の数字の配列を使用できます。最後の数字を出力するには、文字列に変換する必要があります。このようにそれをやって

（woflram alpha: fibonacci 10000）

、あなたは夫婦百万一桁の加算を実行します。それはしばらく時間がかかるかもしれませんが、それは現代のコンピュータが処理するための微風でなければなりません。仕事に行く時間！

Answer 2

フィボナッチのような単純な問題に対して再帰を使わないようにしてください。また、一度だけ使用する場合は、配列を使用してすべての結果を保存しないでください。 2つ前のフィボナッチ数を含む2つの要素の配列で十分です。各ステップで、これらの2つの数値を合計するだけです。 2つの連続したフィボナッチ数をどのように保存できますか？まあ、あなたは2つの連続する整数を持つときには1つが偶数であり、1つが奇数であることを知っています。そのフィーチャを使用してフィボナッチ数を取得/配置する場所を知ることができます。fib(i)の場合、iが偶数（i%2が0）の場合は配列の最初の要素（index 0）に配置し、そうでなければ（i%2は1） 2番目の要素（インデックス1）に配置します。なぜあなたはそれをそこに置くことができますか？あなたがfib(i)を計算しているときに、fib(i)にある値はfib(i-2)になるはずです（(i-2)%2はi%2と同じです）。しかし、fib(i-2)はもう必要ありません。fib(i+1)はまだfib(i-1)（まだ配列に入っています）とfib(i)（配列に挿入されたばかり）が必要です。
ですから、このようなfor loopと再帰呼び出しを置き換えることができます：

int fibonacci(int n){ 
    if(n <= 0){ 
     return 0; 
    } 

    int previous[] = {0, 1};  // start with fib(0) and fib(1) 
    for(int i = 2; i <= n; ++i){ 
     // modulo can be implemented with bit operations(much faster): i % 2 = i & 1 
     previous[i&1] += previous[(i-1)&1]; //shorter way to say: previous[i&1] = previous[i&1] + previous[(i-1)&1] 
    } 
    //Result is in previous[n&1] 
    return previous[n&1]; 
} 

ための時間（関数呼び出し）のプログラミングとressources（スタック）は、それが消費しながら、再帰が実際にdiscommandedされます。だから、あなたが再帰を使うたびに、 "現在の位置"を保存するために必要ならば、単純なポップ/プッシュ操作でループとスタックに置き換えてみてください（C++ではvectorを使うことができます）。フィボナッチの場合、スタックは必要ありませんが、たとえばtree datastructureを反復処理する場合は、スタックが必要です（実装にもよりますが）。私の解決策を探していたとき、私は@naomikがwhileループの解決策を提供しているのを見ました。それも問題ありませんが、私はモジュロ演算（少し短く）で配列を優先します。

今度はサイズlong long intの問題については、大きな数字（たとえば、GMP libraryまたはBoost.multiprecisionなど）の操作を実装する外部ライブラリを使用して解決できます。しかし、あなたはJavaからBigIntegerのようなクラスの独自のバージョンを作成し、私が持っているような基本的な操作を実装することもできます。私は私の例で追加したものだけを実装しました。他のものは実装してみましょう。

主なアイデアは簡単です。BigIntは、little endianの表現を部分的に切り捨てることで大きな10進数を表します（最後にリトルエンディアンが使用される理由を説明します）。これらの部分の長さは、選択したベースによって異なります。 10進表記で作業したい場合は、基数が10の累乗である場合にのみ作用します。：基数として10を選択すると、それぞれが1桁を表します。100（= 10^2） （10^3）として1000を選択すると、各ピースは3桁の連続した数字を表すようになります（リトルエンディアンを参照）。ベースが100の場合、12765は[65, 27, 1]、1789は[89, 17]、505は[5, 5]（= [05,5]）、...ベース1000の場合：12765は[765, 12]、1789は[789, 1]、505 [505]となります。それは最も効率的ではありませんが、それは最も直感的です（私は思う...）
さらには私たちが学校で学んだ紙に加えてのようなビットは次のようになります。

1. 他の1
2. の対応する部分とそれを追加しBigInt
3. の最低の作品で始まりますその合計の最下位ピース（=基底の和のモジュラス）が最終結果の対応する部分になります
4. "大きな"ピースの合計は、次のピースの合計に加算されます（
5. 手順2に進む例えば、次の部分
6. ない片が残っていない場合、（それが左片を有する場合）、キャリーおよび他BigIntの残りの大きな部分を追加

：

9542 + 1097855 = [42, 95] + [55, 78, 09, 1] 
    lowest piece = 42 and 55 --> 42 + 55 = 97 = [97] 
       ---> lowest piece of result = 97 (no carry, carry = 0) 
    2nd piece = 95 and 78 --> (95+78) + 0 = 173 = [73, 1] 
       ---> 2nd piece of final result = 73 
       ---> remaining: [1] = 1 = carry (will be added to sum of following pieces) 
    no piece left in first `BigInt`! 
    --> add carry ([1]) and remaining pieces from second `BigInt`([9, 1]) to final result 
    --> first additional piece: 9 + 1 = 10 = [10] (no carry) 
    --> second additional piece: 1 + 0 = 1 = [1] (no carry) 
==> 9542 + 1 097 855 = [42, 95] + [55, 78, 09, 1] = [97, 73, 10, 1] = 1 107 397 

Hereはどこデモあります私は10000のフィボナッチを計算するために上記のクラスを使用しました（結果は大きすぎてコピーできません）

幸運を祈ってください！

PS：なぜリトルエンディアンですか？実装の容易さのために、数字と繰り返しを追加するときはpush_backを使用できますが、操作の実装は配列の最後の部分ではなく最初の部分から開始されます。