原です。

In message "[ruby-list:18638] fibonacci"
    on 99/11/16, Kazuhiro Yoshida <moriq.kazuhiro / nifty.ne.jp> writes:
|
|もりきゅうです。
|
|sample/fib.rb よりちょい早い版。1 重再帰にしただけですが..
|-- fib2.rb
|def fib(n, i=1, prev=0, this=1)
|  if n == i
|    this
|  else
|    fib n, i+1, this, this+prev
|  end
|end
|print fib(20), "\n"
|--

なるほど。メソッド呼びだし回数が巾乗級だったのが、線形になって激減ですね。
これは、多項漸化式をベクトルと行列を使って2項に直す方法に似ていますね。
それを素朴にやると、こんなふうです。

-----^ fib4.rb
def fib(n)
  if n == 1
    [1, 0]
  else
    x, y = fib(n-1)
    [x + y, x]
  end
end
print fib(20)[0], "\n"
-----$ fib4.rb


|fib2.rb より早いかと思いきやそんなことはなかった読みにくい版。
|
|-- fib3.rb
|# Binet's formula
|def fib(n)
|  root_5 = Math::sqrt 5
|  golden_rate = (1+root_5)/2
|  golden_rate_anti = (1-root_5)/2
|  ((golden_rate ** n - golden_rate_anti ** n)/root_5).to_i
|end
|print fib(20), "\n"

これは漸化式を解いて直接代入しているわけですよね。
でも、最後の int 式は本当は「すぐ近くにある整数」をとらなければならない
ので、


In message "[ruby-list:18740] Re: fibonacci"
    on 99/11/19, Toyofuku <toyofuku / juice.or.jp> writes:
|
|  豊福です。

|    ((golden_rate ** n)/root_5 + 0.5).to_i # 四捨五入
|
|でよいというのを見たことがあるような気がします。

こちらでなくてはだめだと思います。もちろんこっちでも BigFloat で
計算しないとコケますが。



あと、一個の n ではなくて、複数の n に対して fib(n) を求めるなら次の方法
がだんぜん速いでしょう。記憶領域がたくさんいるのだけど。

-----^ fib5.rb
def (Fib = [0, 1]).[](n)
  super || Fib[n] = Fib[n-1] + Fib[n-2]
end
print Fib[20], "*\n"
-----$ fib5.rb