今回は少しだけ数学的な話題を。テーマは「フィボナッチ数列」。どこかで聞いたことはありませんか？
フィボナッチ数列とは？
フィボナッチ数列とは、1202年にイタリアの数学者レオナルド・フィボナッチが発行した『算盤の書』(Liber Abaci) に記載された次の式で表される数列です。
F0 = 0;
F1 = 1;
Fn = Fn-1 + Fn-2
※F0 = 1 としている文献もあります。
つまり、n=2以上のとき、「1つ前と2つ前の和が自分自身」という数列です。実際にフィボナッチ数列を計算すると次のようになります。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
これを「フィボナッチ数」と言います。
数学者フィボナッチは、この増加をはじめ「うさぎの繁殖」にたとえて説明しました。このようにフィボナッチ数はnが大きくなるにつれ、すくすくと確実に成長をしていきます。
フィボナッチ数を求めるプログラムを書いてみる
それでは、n番目のフィボナッチ数を求めるプログラムを、JavaScriptで実装してみましょう。
function fib(no){
if( no < 2 ){
return no;
}else{
return fib(no-1) + fib(no-2);
}
}
すっきりしていますね。このように、JavaScriptでは関数の中から自分自身を呼び出すことができます。これは「再起呼び出し」と呼ばれていて、アルゴリズムを思った通りに記述できる点が便利ですが、実はとても非効率的な方法です。
たとえば、fib(5)の場合、この関数が何度呼び出されるか考えてみましょう。
- fib(5) = fib(4)+fib(3)
- fib(5) = fib(3)+fib(2)+ fib(2)+fib(1)
- fib(5) = fib(2)+fib(1)+fib(1)+fib(0)+ fib(1)+fib(0)+fib(1)
- fib(5) = fib(1)+fib(0)+fib(1)+fib(1)+fib(0)+ fib(1)+fib(0)+fib(1)
たった n=5 の場合でもかなり大変なことになっています。しかし、これくらいなら、最近のCPU演算能力による力技で何とかなるのです。では、これが n=40, n=50くらいになってくるとどうでしょう。さすがに厳しくなってきます。関数の呼び出しには実際の計算と関係のないオーバーヘッドがかかります。計算量より関数呼び出しにCPU処理時間が使われていて、その結果、答えを出すのにものすごく時間が必要になってしまうのです。
「関数呼び出し」を減らそう
ではどうすればよいのか？
先程のコードでは、関数呼び出しがボトルネックになっていましたので、アルゴリズムを少し改良してみます。
function fib2(no){
for(i=0; i<=no; i++){
if( i < 2 ){
data[i] = i;
}else{
data[i] = data[i-1] + data[i-2];
}
}
return data[no];
}
改良したコードでは、一度計算した結果を data[] という配列に格納しています。こうすることで、fib2()そのものは一度しか呼び出されません。
JavaScriptに限らず、配列参照は関数呼び出しに比べてコストがかからない処理なので、高速に実行されるというわけです。
これでも良いのですが、もっといい方法はないのでしょうか？
n番目のフィボナッチ数を求める公式がある
実はフィボナッチ数列には「n番目の値を求める公式」が存在します。
Fn = 1/√5 {((1+√5)/2)^n-((1-√5)/2)^n }
なぜ、整数しかとるはずのないフィボナッチ数にルートが出てくるのかは、数学の奥深いところですが(※この数は「黄金比」に関係があります）、「一般式があるのだから、公式にしたがって関数をつくればいいのでは？」と思いますよね。
確かにそうなのですが、上記の公式では浮動小数点演算や丸めの問題といった新たな要因が発生したり、なにしろ「わかりやすさ」が全く違います。
プログラム言語の限界
また、JavaScriptに限らず、プログラム言語には「限界」があります。fib(103)を計算してみましょう。計算結果は次のようになります。
fib(103) = 1.5005205362068963e+21
そうです。Windowsの電卓でよく見た「もう計算できません」の表示。今回は論理的な話題だったので考えなくてもいいことかもしれませんが、もし将来もっと大きなフィボナッチ数が何らかの意味を持っていてそれを正確に計算する必要性が生じたときどうすればいいでしょう？多倍長整数演算のライブラリを新たに作成したり、それが得意なLISPを使いますか？
困難な問題でも、答えがあるということがわかれば対処策も必ず出てくる
困難な問題に遭遇したとき、得意な誰かにやってもらうという選択があります。計算が得意といえば、Mathematicaですね。
Mathematicaは、理系の方なら一度は使ったこともある数式処理システムのデファクトスタンダードで、このシステムにはFibonacci()というそのまま直球の関数が用意されています。さらにありがたいことに、Mathematicaを作ったスティーブン・ウルフラムは、Wolflam Alphaという数式処理ができる知識エンジンサービスを公開しています。
あなたは、ここにアクセスしてFibonacci(103)と入力するだけで必要なフィボナッチ数の答えを得ることができます。答えを得るだけなら、アルゴリズムのボトルネックをリファクタリングしたり、ゼロからコードを書く必要はまったくないのです。
成長と進化の流れの行き着く先
今回は数学の話でしたが、何かの問題を解決しようとするとき、1)自力でシンプルに解く、2)自力でシンプルな解法を改良する、3)もっとうまくやる人に依頼する、4)専門の道具を使う、という価値変化の流れがあります。人がやっていることはいずれ道具に必ず置き換わりますので、フィボナッチ数列同様、私たちも少しずつ「成長」していきたいものですね。
