RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい - prime's diary

qiita.com mattn.kaoriya.net という記事を読んだのでアルゴリズムを改善して速くしました。 いわゆる行列累乗のテクニックを使うと（乗算部分を除けば）N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら、高速フーリエ変換を使えば)。 単純な足し算のループでは足し算の桁数を考えると なのでそれよりは随分と速くなります。 40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。 こちらが元のソースコード def fib(n) f0, f1, v = 0, 1, 0 n.times do |x| if x <= 1 v = x else v = f0 + f1 f0, f1 = f1, v end end return f0 + f1

[u1tnk]

なるほどわからん！すげえ！

[tanakh]

これだと桁数が大きくて多倍長演算のウェイトが大きいからＲｕｂｙでもＧｏよりそんなに遅くないんじゃないかって思ったけど、Ｒｕｂｙの多倍長の乗算ＦＦＴ使ってなかった気もするしどうなんだろ。

[k2wanko]

はやい

[kamipo]

はやい

[Nyoho]

対角化して

[syuu1228]

絶対こういう指摘入るんだろうなぁって思ってたら：RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい - prime's diary

[daikikohara]

次に早くした人のエントリーはどこだろう？

[Pasta-K]

なるほど