Tbpgr Blog

Employee Experience Engineer tbpgr(てぃーびー) のブログ

アルゴリズム | 冪剰余の計算

概要

冪剰余の計算

内容

冪乗の剰余を計算。
書籍「アルゴリズムを学ぼう」より。
書籍のサンプルはJavaのコードだったが、Rubyで書いてみた。

1.オーソドックスに計算
2.a*b mod c = (a mod c) * (a mod c) mod c を利用
3.2の計算中の個別の結果を再利用して、再起呼び出しにする

べた書き版

ソース
# encoding: utf-8
require "./bench"

class Fixnum
  def pow_mod(pow, divide)
    self ** pow % divide
  end
end

_benchmark{p 3.pow_mod((2**22),4)}
計測結果
1.357000   0.047000   1.404000 (  1.398080)

経過剰余版

ソース
# encoding: utf-8
require "./bench"

class Fixnum
  def pow_mod(pow, divide)
    i = 0
    ret = 1
    (1..pow).each do |n|
      ret = (ret * self) % divide
    end
    ret
  end
end
_benchmark{p 3.pow_mod((2**22),4)}
計測結果
0.297000   0.000000   0.297000 (  0.297017)

結果変数流用版

ソース
# encoding: utf-8
require "./bench"

class Fixnum
  def pow_mod(pow, divide)
    return 1 if pow == 0
    result = self.pow_mod(pow / 2, divide)
    result = result * result % divide
    result = result * self % divide if pow % 2 == 1
    return result
  end
end
_benchmark{p 3.pow_mod((2**22),4)}
計測結果
0.000000   0.000000   0.000000 (  0.001000)

おまけ

計測用bench.ruby

require "benchmark"

def _benchmark(&block)
  return unless block_given?
  ret = Benchmark.measure(&block)
  puts "#{ret.to_s}"
end

備考

Rubyオープンクラスで組み込みメソッドであるかのように書けるのが心地よい