Rubyには、最大公約数を求めるInteger#gcd と Integer#gcd2がある。
「gcd"2"ってなんやねん！」と気になったので、実装を見てみた。

ruby>>

File lib/mathn.rb, line 19

def gcd2(int)
a = self.abs
b = int.abs
a, b = b, a if a < b

pd_a = a.prime_division
pd_b = b.prime_division

gcd = 1
for pair in pd_a
  as = pd_b.assoc(pair[0])
  if as
    gcd *= as[0] ** [as[1], pair[1]].min
  end
end
return gcd

end
<<ruby

2数を因数分解し、どちらにもある数をかけていくと言う強引なものだった。

ついでにInteger#gcdのほうも見てみた。
ruby>>

File lib/rational.rb, line 438

def gcd(other)
min = self.abs
max = other.abs
while min > 0
tmp = min
min = max % min
max = tmp
end
max
end
<<ruby

コチラは、ユークリッドの互除法。
シンプルだ。

参考までに、この2つに関してベンチマークしてみた。

• コード
  ruby>>
  require 'mathn'
  require 'benchmark'

Benchmark.bm do |x|
x.report("Integer#gcd :"){ 12345.gcd(123456789) }
x.report("Integer#gcd2:"){ 12345.gcd2(123456789) }
end
<<ruby

• 結果
  ruby>>
  user system total real

Integer#gcd : 0.000000 0.000000 0.000000 ( 0.000000)
Integer#gcd2: 0.516000 0.000000 0.516000 ( 0.516000)
<<ruby

結果は当たり前といったら当たり前なんやけども、Integer#gcd2のほうが遅かった。

何でInteger#gcdとInteger#gcd2の2つが存在するんやろ・・・。

というか、Integer#gcd2が何で存在しているのかが不思議！！

何かメリットでもあるんやろか・・・？