mzp https://blog.hatena.ne.jp/mzp/ みずぴー日記 https://mzp.hatenadiary.org/ Haskell 30分プログラム 30分プログラム、その581。対数ステップでフィボナッチ数を計算できるらしいので、やってみる。 SICPの演習問題で担当になったところに、フィボナッチ数を対数ステップで計算するアルゴリズムが載っていたので試してみた。とりあえず、配布資料を貼って置きますね。 対数ステップでフィボナッチ数を計算するアルゴリズムが存在する。fib-iterではaa := a + b、b := aという変形を行なっていた。 この変形をTと呼ぶと、Tはn回適用されている。 つまり、(1,0)にT^nを適用すると、Fib(n+1)とFib(n)が得られる。ここで、Tを a := bq + aq + ap b := bp … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmzp.hatenadiary.org%2Fentry%2F20090512%2Ffib" title="対数ステップでフィボナッチ数を計算する - みずぴー日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-05-12 00:00:00 rich https://mzp.hatenadiary.org/entry/20090512/fib 1.0 100%