Fibonacci Sequence

フィボナッチ数列は各項が前の 2 項の和である数列（0,1,1,2,3,5,8...）であり、黄金比と関係し、自然界とアルゴリズムに広く現れる。

目的

増加パターンを記述し、自然現象やアルゴリズムの複雑度解析に現れる。

メカニズム

F(0)=0、F(1)=1、F(n)=F(n-1)+F(n-2)。閉形式（ビネの公式）：F(n)=(φ^n-ψ^n)/√5、φ=(1+√5)/2 が黄金比。行列べき乗や高速倍増法で O(log n) で計算できる。素朴な再帰は O(φ^n) で指数的に遅い。

ユースケース

アルゴリズムの複雑度解析
テクニカル指標の計算（フィボナッチ・リトレースメント）
自然パターンのモデリング
DP（動的計画法）の教育

例

入力
```
F(10)
```
Output
```
55
```
0,1,1,2,3,5,8,13,21,34,55

よくあるエラー

Naive recursion recomputes subproblems and runs exponentially slow: Use memoization or fast matrix exponentiation

関連用語

階乗 n! = n×(n-1)×...×1 は順列と組合せの基礎である。極めて速く増大し、20! はすでに 64 ビット整数の範囲を超える。

ビッグ O 記法は関数の漸近的上界を表し、定数と低次の項を無視してアルゴリズムの時間・空間計算量を分析するのに使われる。

BigInteger は任意精度の整数型であり、固定ワードサイズに制限されず、ネイティブ整数の範囲を超える計算（暗号や組合せ論など）に使われる。

関連ツール

高精度計算ツール

High-precision arithmetic calculator. No floating-point errors。無料、プライベート、100%クライアントサイド。

フィボナッチ数列ジェネレーター

Fibonacci Generator — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

References