フィボナッチ数列の百番目

Fibonacci数列の百番目の値が欲しいと思ったらどうするだろうか。ある日そう思ったのは、この本に手書きで計算しているノートがあったから

数学ガール 下 (MFコミックス フラッパーシリーズ)

ちょっとその辺に聞いてみたら、手元にコンピュータあるの前提でなんかプログラムするとか言う人が多かった。計算機環境がいつでもあると思い込んでるのは良くないと思う。グーグルで計算して出てきたらラッキーとか言う奴(あとでやってみたけど出てきません、グーグル電卓)、いつでもネットリーチャブルなのかほんとに。ちょっと感心したのは、取り敢えず手元を grep で検索するというの、絶対昔やってるから、やってない筈ないからと。

でも手書き計算するのはちょっと、とても、大変そうだ。

Rubyスクリプト(irb)

まあそういうわけで Ruby で計算する、クラスとかモジュールとか定義しないでいいよね、irb で何とかなるよね。

素朴なこれは 100項となると何処かに行ってしまって帰ってこない。

irb(main):004:0> def fib(n)
irb(main):005:1>   case n
irb(main):006:2>     when 0,1 then 1
irb(main):007:2>     else fib(n-1) + fib(n-2)
irb(main):008:2>     end
irb(main):009:1>   end
=> nil
irb(main):010:0> fib(1)
=> 1
irb(main):011:0> fib(2)
=> 2
irb(main):012:0> fib(5)
=> 8
irb(main):013:0> fib(10)
=> 89
irb(main):014:0> fib(100)
IRB::Abort: abort then interrupt!!

途中までの計算結果を何処かに憶える様にしないと計算が爆発する。といってもインスタンス変数やクラス変数に持ってくるにはクラスとかモジュールとか定義しないといけない。
どうせ憶えさせるなら配列なので、その配列自身に計算させればいいのだろう。

irb(main):005:0> fib = [1, 1]
=> [1, 1]
irb(main):006:0> def fib.[](n)
irb(main):007:1>   self.at(n) ? self.at(n) : self[n] = self[n-1] + self[n-2]
irb(main):008:1>   end
=> nil
irb(main):009:0> fib[2]
=> 2
irb(main):010:0> fib
=> [1, 1, 2]
irb(main):011:0> fib[100]
=> 573147844013817084101

はじめ Array#［］ メソッドを上書きするの躊躇して別の名をつけていたんだけど、Array#at メソッドを思い出してこうした。何気に Array#［］= メソッドはどちらとも違うメソッドなの、そしてそれ(［］=)を使ってるの注意。(「［］」全角半角注意)

ちなみに結果として得られる百項は

irb(main):011:0> fib[100]
=> 573147844013817084101
irb(main):012:0> fib
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4
181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 83
2040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 18
36311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280
099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 5912867
29879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842,
 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141,
 117669030460994, 190392490709135, 308061521170129, 498454011879264, 80651553304
9393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 89
44394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 6130579
0721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140
727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067
194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19
740274219868223167, 31940434634990099905, 51680708854858323072, 8362114348984842
2977, 135301852344706746049, 218922995834555169026, 354224848179261915075, 57314
7844013817084101]

それにしても、この本で手書きノートを書いていたのはどなたなんだろう。勿論登場人物が書いたんだけど、原稿描いたのは、或はそのまた資料とか。