为什么二进制 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算法比Euclid算法更复杂，并且涉及较低级别的操作，因此当用Ruby等高级语言实现时，它会受到更多解释开销的影响。
2. 现代计算机往往具有快速除法（和模）指令，使得标准欧几里得算法难以与之竞争。

Answer 2

在现代消费级硬件（M1 Mac Mini、AMD Ryzen 5600X）上，似乎在某些情况下 Euclid 算法表现优异，而在某些情况下二进制 GCD 算法表现优异。我不认为这与 Ruby 有任何关系，因为我使用的是 Go。在某些情况下，我发现两者在性能上存在显着差异（对于 64 位整数）：

米	n	二进制	欧几里得
360	92822	14.2 纳秒/操作	9.6 纳秒/操作
123456789	987654321	29.3 纳秒/操作	3.8 纳秒/操作
9223372036854775806	9223372036854775807	129.5 纳秒/操作	3.8 纳秒/操作
63245986	102334155	27.1 纳秒/操作	120.4 纳秒/操作
614889782588491410	693386350578511590	4.8 纳秒/操作	6.6 纳秒/操作

第一行是一个小合数和一个质数+1。第二行只是按顺序排列的数字，然后颠倒过来。第三行是 2⁶³−2 和 2⁶³−1。第四行是两个连续的斐波那契数。第五行是（大部分）连续素数的两个大乘积（2×3×5×···）。

我的一般观察是，在常见情况下，二元 GCD 比欧几里得算法稍微快，但在病态情况下，它们会互相击败。

我运行了几次基准测试，结果相当稳定。与任何微基准一样，这些数字只是说明性的。