timeline フィボナッチ数列計算機 star

フィボナッチ数列はどう計算する?

フィボナッチ数列は単純な漸化式で定義されます: F(0) = 0、F(1) = 1、そしてそれ以降の各項はその直前の2項の和になります。F(n) = F(n-1) + F(n-2)。このたった1つの規則から0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…が生成されます — どの数も直前の2つを足しただけなので、最初の十数項程度なら手計算で簡単に検証できます。

あまり知られていないのが、数の増え方がいかに速いかということです。F(30)の時点ですでに80万を超え、F(100)は21桁の数になります。ほとんどの電卓や、素のJavaScriptの数値が使う標準的な64ビット数値型は、整数が約9 × 10^15を超えると気づかないうちに精度を失います — フィボナッチ数列はこの閾値におよそ第78項で到達します。それを超えると、単純な電卓は何の警告もなく丸められたわずかに誤った答えを表示してしまいます。このツールは、すべての項をBigInt演算で計算することでこの問題を完全に回避します。BigIntは、nがどれほど大きくなっても任意の大きさの整数を1桁ずつ正確に表現できるため、F(100)、F(500)、さらにはF(1000)でさえ最後の桁まで正確に求まります。

もう1つのよく知られた性質が黄金比との関係です。nが大きくなるにつれ、連続する項の比F(n)/F(n-1)はφ ≈ 1.6180339887…に収束していきます。この定数は正五角形の比率にも、再帰を使わずにフィボナッチ数を計算するビネの公式にも登場します。序盤の項ではこの比率は大まかにしか近似しません(3/2 = 1.5、8/5 = 1.6)が、およそ第15項の時点ですでに小数点以下4桁まで正確になります。

知っておくべきこと

• 添字の慣習。一部の資料では数列をF(0) = 0ではなくF(1) = F(2) = 1から始めます。このツールは、ほとんどの教科書やコンピュータサイエンスの授業でも使われる標準的な数学の慣習、F(0) = 0、F(1) = 1に従います。
• 増加率。各項は直前の項のおよそ1.618倍になるため、桁数はnに対してほぼ線形に増加します — F(1000)は200桁を超え、まさに浮動小数点の電卓が破綻しBigIntが必要になる範囲です。
• よくある落とし穴。標準的な浮動小数点数を使う表計算ソフトや電卓(素のJavaScriptやExcelなど)から、およそ第78項を超える大きなフィボナッチ値をコピーすると、末尾の数桁が気づかないうちに丸められてしまいます — 非常に大きな値は必ず任意精度演算に対応したツールと照合してください。
• 実用的な使い道。純粋数学以外にも、この数列はアルゴリズム解析(フィボナッチ探索、動的計画法の教材例)、自然界のある種の成長パターンの記述、金融のテクニカル分析で使われるリトレースメント水準などに登場します。