稲葉です。
本論には口を出せないので、ちょっとしたところに口をはさみます。

EGUCHI Osamu wrote:

> keiju> class Integer
> keiju>   def gcd(int)
> keiju>     a = self.abs
> keiju>     b = int.abs
> keiju>
> keiju>     a, b = b, a if a < b
> keiju>
> keiju>     while b != 0
> keiju>       void, a = a.divmod(b)
> keiju>       a, b = b, a
> keiju>     end
> keiju>     return a
> keiju>   end
> keiju> end
> keiju>
> keiju> コストがかかるのは, whileループですが, 小さい数で大きい数をdivmodしつ
> keiju> づけるだけですから, ループの数はそんなに大きくないかと...
> 
> そう言えば、これの再帰版の
> 
>   def gcd(int)
>   return self if int == 0
>   int.gcd(self % int)
>   end
> 
> ってテールリカージョンの典型で載ってますね^^;;;;;;;

石塚さんもえぐちさんもCはあまりお使いでないのでしょうか？
自分はCの予約語を変数に使われるといったん構文解析に失敗します:->

> あと、while に入る前に、
> 
>   q = a | b
>   while (q & 1) == 0
>     a >>= 1
>     b >>= 1
>   end

 q = a | b または q >>= 1をループに入れないと抜け出せないような。。。
 while a[0] == 0 && b[0] == 0 の効率がいいと思います

むかしどこかで読んだ割り算を使わないGCDです。

class Integer
  def gcd(n)
    m = self
    b = 0
    while n[0]==0 && m[0]==0
      b+=1; n>>=1; m>>=1
    end
    m>>=1 while m[0]==0
    n>>=1 while n[0]==0
    while m!=n
      m, n = n, m if n > m
      m -= n; m>>=1 while m[0]==0
    end
    m<<b
  end
end
--
			稲葉 浩人 <inaba / st.rim.or.jp>