为什么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快很多？

回答

相关问题