RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい

qiita.com

mattn.kaoriya.net

という記事を読んだのでアルゴリズムを改善して速くしました。

いわゆる行列累乗のテクニックを使うと（乗算部分を除けば）N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら、高速フーリエ変換を使えば)。 単純な足し算のループでは足し算の桁数を考えると なのでそれよりは随分と速くなります。

40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。

こちらが元のソースコード

def fib(n)
  f0, f1, v = 0, 1, 0
  n.times do |x|
    if x <= 1
      v = x
    else
      v = f0 + f1
      f0, f1 = f1, v
    end
  end
  return f0 + f1
end

puts fib(1000000)

実行してみます。

$ ruby fib_naive.rb > /dev/null
ruby fib_naive.rb > /dev/null  9.63s user 0.87s system 100% cpu 10.499 total

行列累乗を用いたソースコード。行列を累乗するところで再帰を使っています。

def mat_mul(lhs, rhs)
  res = [[0,0],[0,0]]
  2.times {|i| 2.times {|j| 2.times {|k|
    res[i][j] += lhs[i][k] * rhs[k][j]
  }}}
  return res
end

def mat_pow(mat, index)
  if index == 1
    return mat
  else
    half = mat_pow(mat, index / 2)
    if (index % 2) == 0
      return mat_mul(half, half)
    else
      return mat_mul(half, mat_mul(half, mat))
    end
  end
end

def fib(n)
  return mat_pow([[1,1],[1,0]], n-1)[0][0]
end

puts fib(1000000)

$ ruby fib.rb > /dev/null
ruby fib.rb > /dev/null  0.10s user 0.01s system 97% cpu 0.106 total

さらに100倍ぐらい速くなりました！すごい！