O(log n)でフィボナッチ数を求める

O(log n)でフィボナッチ数のN番目を求める方法をRubyで実装してみました。この間のSICP勉強会で教えてもらったやつです。
まず普通のフィボナッチ数。こいつはO(n)です。

def fib1(n)
  a, b = 0, 1
  n.times do
    a, b = a + b, a
  end
  a
end

O(log n)版のフィボナッチ数。なんでこれでフィボナッチ数が求められるかは、ここを参照してください。ちなみにRubyのMatrixの**は、O(log n)で実装されています。

require 'matrix'

def fib2(n)
  a = Matrix[[1, 1], [1, 0]]
  b = Matrix[[0], [1]]
  (a ** n * b)[0, 0]
end

こんな感じでベンチマークをとってみました。

require 'benchmark'

n = 100_000
Benchmark.bm do |x|
  x.report("fib1(#{n}):") { fib1(n) }
  x.report("fib2(#{n}):") { fib2(n) }
end

      user     system      total        real
fib1(100000):  2.653000   0.370000   3.023000 (  3.284000)
fib2(100000):  0.391000   0.000000   0.391000 (  0.391000)

んー、10万くらいだとオーダーの差を感じられますね。