为什么二进制GCD算法对我来说慢得多

Question

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

根据维基百科的说法，它应该比欧几里得的算法快一点(不多，但我至少希望能获得同样的性能(。对我来说，它慢了一个数量级。你们能帮我弄清楚为什么吗？

我试着在Ruby中实现它。首先，我使用递归解决方案

def gcd_recursive(u, v)
return u|v if u==0 or v==0
if u.even?
  if v.even?
    return gcd(u>>1, v>>1)<<1
  else
    return gcd(u>>1, v) if v.odd?
  end
elsif u.odd? and v.even?
  return gcd(u, v>>1)
else
  if u < v
    u, v = v, u
  end
  return gcd((u-v)>>1, v)
end
end

这并没有很好地工作，所以我想检查一下如果它是一个循环会有多快

def gcd(u, v)
  return u|v if u==0 or v==0
  shift=0
  while ((u|v)&1)==0 do
    u=u >> 1;
    v=v >> 1;
    shift += 1
  end
  while ((u&1) == 0) do 
    u=u >> 1
  end
  begin
    while ((v & 1) == 0) do
      v=v >> 1
    end
    if u < v
      v -= u
    else
      diff = u - v
      u = v
      v = diff
    end
  end while v != 0
  u<<shift
end

这些是的基准结果

       user     system      total        real
std  0.300000   0.000000   0.300000 (  0.313091)
rbn  0.850000   0.000000   0.850000 (  0.872319)
bin  2.730000   0.000000   2.730000 (  2.782937)
rec  3.070000   0.000000   3.070000 (  3.136301)

std是原生的ruby 1.9.3 C实现。

rbn基本上是一样的(欧几里得的算法(，但用Ruby编写。

bin是您在上面看到的循环代码。

rec是递归版本。

编辑：我在matz的ruby 1.9.3上运行了基准测试。我试着在Rubinius上运行同样的测试，结果就是这样。这也令人困惑。。。

 rbn  1.268079   0.024001   1.292080 (  1.585107)
 bin  1.300082   0.000000   1.300082 (  1.775378)
 rec  1.396087   0.000000   1.396087 (  2.348785)

Answer 1

这只是一个猜测，但我怀疑这是两个原因的结合：

1. 二进制GCD算法比欧几里得算法更复杂，并且涉及较低级别的操作，因此在Ruby等高级语言中实现时，它会遭受更多的解释开销
2. 现代计算机往往具有快速除法(和模(指令，这使得标准欧几里得算法难以与之竞争