爲什麼python實現miller-rabin的速度比ruby快很多？

對於我的一個類，我最近遇到了使用miller-rabin算法來確定20到29000之間素數的ruby和python實現。我很好奇爲什麼即使它們看起來是相同的實現， python代碼運行得非常快。我已經讀過python通常比ruby更快，但速度差別有多大？爲什麼python實現miller-rabin的速度比ruby快很多？

miller_rabin.rb

def miller_rabin(m,k) 
    t = (m-1)/2; 
    s = 1; 
    while(t%2==0) 
    t/=2 
    s+=1 
    end 

    for r in (0...k) 
    b = 0 
    b = rand(m) while b==0 
    prime = false 
    y = (b**t) % m 
    if(y ==1) 
    prime = true 
    end 

    for i in (0...s) 
     if y == (m-1) 
     prime = true 
     break 
     else 
     y = (y*y) % m 
     end 
    end 

    if not prime 
    return false 
    end 
    end 
    return true 
end 

count = 0 
for j in (20..29000) 
    if(j%2==1 and miller_rabin(j,2)) 
    count+=1 
    end 
end 
puts count

miller_rabin.py：

import math 
    import random 

    def miller_rabin(m, k): 
     s=1 
     t = (m-1)/2 
     while t%2 == 0: 
      t /= 2 
      s += 1 

     for r in range(0,k): 
      rand_num = random.randint(1,m-1) 
      y = pow(rand_num, t, m) 
      prime = False 

      if (y == 1): 
       prime = True 


      for i in range(0,s): 
       if (y == m-1): 
        prime = True 
        break 
       else: 
        y = (y*y)%m 

      if not prime: 
       return False 

     return True 

    count = 0 
    for j in range(20,29001): 
    if j%2==1 and miller_rabin(j,2): 
     count+=1 

    print count

當我測量每個用測量命令在Windows PowerShell中的執行時間，我得到如下：

Python 2.7：
Ticks：4874403
總毫秒數：487.4403

的Ruby 1.9.3：
蜱：682232430
總毫秒：68223.243

我將不勝感激任何見解誰能給我到爲什麼他們是如此巨大的差異

來源

2013-04-07 user2255192

我只是分析Ruby代碼，看看是否顯示任何東西。 – 2013-04-07 20:06:07

請注意，您應該在Python 2中將'range'更改爲'xrange'。'range'不必要地*分配一個數字列表。 – user4815162342 2013-04-07 20:36:30

我覺得這些剖析結果要回答你的問題：

%self  total  self  wait child calls name 
96.81  43.05 43.05  0.00  0.00 17651 Fixnum#** 
1.98  0.88  0.88  0.00  0.00 17584 Bignum#% 
0.22  44.43  0.10  0.00 44.33 14490 Object#miller_rabin 
0.11  0.05  0.05  0.00  0.00 32142 <Class::Range>#allocate 
0.11  0.06  0.05  0.00  0.02 17658 Kernel#rand 
0.08  44.47  0.04  0.00 44.43 32142 *Range#each 
0.04  0.02  0.02  0.00  0.00 17658 Kernel#respond_to_missing? 
0.00  44.47  0.00  0.00 44.47  1 Kernel#load 
0.00  44.47  0.00  0.00 44.47  2 Global#[No method] 
0.00  0.00  0.00  0.00  0.00  2 IO#write 
0.00  0.00  0.00  0.00  0.00  1 Kernel#puts 
0.00  0.00  0.00  0.00  0.00  1 IO#puts 
0.00  0.00  0.00  0.00  0.00  2 IO#set_encoding 
0.00  0.00  0.00  0.00  0.00  1 Fixnum#to_s 
0.00  0.00  0.00  0.00  0.00  1 Module#method_added

看起來比Python的像Ruby的**操作很慢。

看起來像(b**t)通常太大而無法在Fixnum中修復，因此您使用的是Bignum（或任意精度）算法，該算法速度要慢得多。

來源

2013-04-07 20:09:52

謝謝，我沒有意識到這是在引擎蓋下。它絕對清除了我的一些混淆 – user2255192 2013-04-08 19:54:47

在ruby中，您使用的是(a ** b) % c來計算取冪的模。在Python中，您使用的是更有效的三元素pow電話，其文檔字符串明確規定：

三個參數，相當於(x**y) % z，但可能會更有效（例如，對於多頭）。

您是否想要指望這種內置運算符對紅寶石的缺乏是一個意見問題。一方面，如果紅寶石沒有提供，你可能會說速度要慢得多。另一方面，你不是在算法上測試同樣的東西，所以有人會說比較不公平。

一個快速的谷歌搜索結果顯示there are implementations的模冪指數爲紅寶石。

來源

2013-04-07 20:26:44 user4815162342

謝謝！這絕對有助於爲我解決一些困惑 – user2255192 2013-04-08 19:53:04

爲什麼python實現miller-rabin的速度比ruby快很多？

回答

相關問題