整数の公式でフィボナッチ数列を求めるという記事を読んで、 「これコンパイル時ならGoでも簡単に計算できるのでは?」と思いやってみたメモ。
背景
みんな大好きフィボナッチ数列(要出典)。 漸化式で定義されているため、再帰やループを使って書くことが多いと思いますが、 閉じた式で書くことが知られています。 ただし、この一般式には無理数の演算が入るので、コンピュータで厳密に扱うことはできません。 ところが、さきほど紹介した記事で紹介された方法を使うと、整数の演算のみで実現できるそうです。
原理などはネタ元の記事を参照してもらうとして、 Python3では以下のように書けるらしいです。
1 2 |
|
ある程度大きなフィボナッチ数を求める場合、 計算途中の値が非常に大きくなるため、多倍長整数が必要となります。 Python3は多倍長整数に組み込みで対応していますが、 Goではmath/bigパッケージを利用する必要があります。
なんか面倒だなGolangと思っていたのですが、 Better C - Go言語と整数 #golangを読んで、 「Goの定数には型がない(場合がある)」「任意の精度で計算してくれる」ということを知り、 「つまりコンパイル時に定数として計算すれば楽にいけるのでは!!」と考えたわけです。
結果
ちょっと複雑な式ですが、個々の演算自体はPython3もGoも変わらないので、 翻訳は簡単ですね。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
|
実行結果です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
Fibxxx
をたくさん書くのはつらかったので、ソースコードはPerlで自動生成しました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
21までしかないのは、 22以降を求めようとしたらコンパイルが通らなかったためです。
1 2 3 |
|
どうやら512bitまでしか扱えないらしい。 任意精度扱えるって書いてあったのに!!!
おとなしく多倍長整数が組込の言語でやれっている話ではありますが、 なんとなくやってみたかったんです。
参考
ネタ元にある「母関数」という概念は、数学ガールを読んで知りました。
フィボナッチ数列に触れている部分はWebでも公開されているので、そちらもどうぞ(ミルカさんとフィボナッチ数列)