概要
冪剰余の計算
内容
冪乗の剰余を計算。
書籍「アルゴリズムを学ぼう」より。
書籍のサンプルは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