O(log n)の累乗

Ruby

ついでにO(log n)の累乗も書いてみました。負数はあつかえません。負だったら符号を反転とかする必要があるのですが、手抜きしてます。
O(n)版。

def pow1(n, m)
  (0 ... m).inject(1) {|a, i| a * n }
end

O(log n)版。

def pow2(n, m)
  a = 1
  while m > 0
    d, r = m.divmod(2)
    if r.zero?
      n, m = n ** 2, d
    else
      a, m = a * n, m - 1
    end
  end
  a
end

ベンチマーク。

require 'benchmark'

n = 2
m = 100_000
Benchmark.bm(20) do |x|
  x.report("pow1(#{n}, #{m}):") { pow1(n, m) }
  x.report("pow2(#{n}, #{m}):") { pow2(n, m) }
  x.report("#{n} ** #{m}:    ") { n ** m     }
end

結果。

                          user     system      total        real
pow1(2, 100000):      3.124000   0.580000   3.704000 (  3.925000)
pow2(2, 100000):      0.000000   0.000000   0.000000 (  0.000000)
2 ** 100000:          0.000000   0.000000   0.000000 (  0.000000)