4

对于我的一个课程，我最近遇到了使用 miller-rabin 算法来识别 20 到 29000 之间的素数的 ruby​​ 和 python 实现。我很好奇为什么，即使它们看起来是相同的实现，python代码运行得更快。我已经读到 python 通常比 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 中使用 Measure-Command 测量每个的执行时间时，我得到以下信息：

Python 2.7：
滴答声：4874403
总毫秒数：487.4403

Ruby 1.9.3：
滴答声：682232430
总毫秒数：68223.243

I would appreciate any insight anyone can give me into why their is such a huge difference

4

2 回答 2

7

In ruby you are using (a ** b) % c to calculate the modulo of exponentiation. In Python, you are using the much more efficient three-element pow call whose docstring explicitly states:

With three arguments, equivalent to (x**y) % z, but may be more efficient (e.g. for longs).

Whether you want to count the lack of such built-in operator against ruby is a matter of opinion. On the one hand, if ruby doesn't provide one, you might say that it's that much slower. On the other hand, you're not really testing the same thing algorithmically, so some would say that the comparison is not fair.

A quick googling reveals that there are implementations of modulo exponentiation for ruby.

于 2013-04-07T20:26:44.533 回答
2

I think these profile results should answer your question:

%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

Looks like Ruby's ** operator is slow as compared to Python.

It looks like (b**t) is often too big to fix in a Fixnum, so you are using Bignum (or arbitrary-precision) arithmetic, which is much slower.

于 2013-04-07T20:09:52.230 回答