c++ - n 番目のフィボナッチ数を出力 [最大 1000 桁]

Question

C/C++で n 番目のフィボナッチ数を計算するにはどうすればよいですか? フィボナッチ数には最大 1000 桁まで含めることができます。最大 2^64 (unsigned long long) の数値を生成できます。それが数の限界なので、私はそれを行う他の方法が必要だと推測しています-私は知りません.

編集：

また、外部ライブラリを使用せずに実行する必要があります。

Answer 1

あなたはまだ始めたとは言っていないので、いくつかヒントを出します。

千桁は多いです。C または C++ の組み込み数値型よりも多くの値を保持できます。

これを回避する 1 つの方法は、任意精度の数学ライブラリを使用することです。これには、基本的に数字に必要な桁数を与える構造があります。

もう 1 つの方法は、独自のキャッシュ アンド キャリーをロールすることです。

unsigned short int term1[1024];  // 1024 digits from 0-9
unsigned short int term2[1024];  // and another

unsigned short int sum[1024];    // the sum

addBigNumbers(&term1, &term2, &sum);   // exercise for the reader

のアルゴリズムは次のaddBigNumbersようになると思います。

Start at the ones digit (index 0)
Add term1[0] and term2[0]
Replace sum[0] with the right digit of term1[0] + term2[0] (which is ... ?)
Keep track of the carry (how?) and use it in the next iteration (how?)
Repeat for each digit

フィボナッチ数列を計算しているので、これらの大きな数を再利用して数列の次の項に到達できます。それらをコピーするのではなく、 を繰り返し呼び出すと、どれが項でどれが合計であるかを変更する方が速いことに気付くかもしれませんaddBigNumbers。

Answer 2

任意の大きな整数に対してGMPを使用してみることができます。