爲什麼二進制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基本上是一樣的東西（Euclid的算法），但用Ruby編寫。

bin是您在上面看到的循環代碼。

rec是遞歸版本。

編輯：我跑了matz'紅寶石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. 現代計算機往往具有快速分割（和模）指令，使得標準歐幾里得算法很難與之競爭。