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

   1  # File lib/mathn.rb, line 19
   2    def gcd2(int)
   3      a = self.abs
   4      b = int.abs
   5      a, b = b, a if a < b
   6      
   7      pd_a = a.prime_division
   8      pd_b = b.prime_division
   9      
  10      gcd = 1
  11      for pair in pd_a
  12        as = pd_b.assoc(pair[0])
  13        if as
  14          gcd *= as[0] ** [as[1], pair[1]].min
  15        end
  16      end
  17      return gcd
  18    end

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

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

   1  # File lib/rational.rb, line 438
   2    def gcd(other)
   3      min = self.abs
   4      max = other.abs
   5      while min > 0
   6        tmp = min
   7        min = max % min
   8        max = tmp
   9      end
  10      max
  11    end

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

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

• コード

     1  require 'mathn'
     2  require 'benchmark'
     3  
     4  Benchmark.bm do |x|
     5    x.report("Integer#gcd :"){ 12345.gcd(123456789) }
     6    x.report("Integer#gcd2:"){ 12345.gcd2(123456789) }
     7  end
  

• 結果

     1        user     system      total        real
     2  Integer#gcd :  0.000000   0.000000   0.000000 (  0.000000)
     3  Integer#gcd2:  0.516000   0.000000   0.516000 (  0.516000)
  

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

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

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

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