フィボナッチ数を計算する

前に書いたトリボナッチ数と同じようなやり方でフィボナッチ数を計算する方法。
自分が調べた範囲では、フィボナッチ数を計算する一番速いアルゴリズムだと思う。

フィボナッチ数 とリュカ数 を

で定義する。

リュカ数を次の漸化式から計算して
、
フィボナッチ数は

により求める。

言語は Ruby。

# フィボナッチ数(とリュカ数)を計算
# 添え字は負でもよい
class Fibonacci
  def initialize
    @memo = {-1=>-1, 0=>2, 1=>1}
  end

  def fib(n)
    m = n / 2
    if n.even? then
      (luc(m) + 2 * luc(m - 1)) * luc(m) / 5
    else
      (2 * luc(m) + luc(m + 1)) * luc(m) / 5 + (m.even? ? -1 : 1)
    end
  end

  def luc(n)
    @memo[n] ||= begin
      m = n / 2
      s = m.even? ? 1 : -1
      n.even? ? luc(m) ** 2 - 2 * s : luc(m) * luc(m + 1) - s
    end
  end
end

fibonacci = Fibonacci.new
# F_100 と L_100 を出力
p fibonacci.fib(100)
p fibonacci.luc(100)

fib のところは

  def fib(n)
    (luc(n) + 2 * luc(n - 1)) / 5
  end

と書いても結果は変わらないけど、これだと遅くなるので、luc(n) と luc(n-1) のところに下のメソッドの式を突っ込んで変形したのが上のコード。