フィボナッチ数列に関する３つのアルゴリズムの速度比較＠Ruby - 簡潔なQアルゴリズムの違いが速度に明確に表れるわかりやすい例のひとつであるフィボナッチ数列を使って速度比較。 気軽に多倍長が使える言語でないと、線形とlogの違いは見えづらい。 #!/usr/bin/ruby -Ku require 'matrix' def fib_recursive(n) case n when 0 return 0 when 1 return 1 else return fib_recursive(n-1)+fib_recursive(n-2) end end def fib_linear(n) a, b = 0, 1 n.times do a, b = b, a+b end return a end def fib_log(n) (Matrix[[1,1],[1,0]]**n)[0,1] end def omit_bignum(n, dig = 20) s = n.to_s
