Why python implementation of miller-rabin faster than ruby by a lot?

Question

For one of my classes I recently came across both a ruby and a python implementations of using the miller-rabin algorithm to identify the number of primes between 20 and 29000. I am curious why, even though they are seemingly the same implementation, the python code runs so much faster. I have read that python was typically faster than ruby but is this much of a speed difference to be expected?

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

When I measure the execution time of each using Measure-Command in Windows Powershell, I get the following:

Python 2.7:
Ticks: 4874403
Total Milliseconds: 487.4403

Ruby 1.9.3:
Ticks: 682232430
Total Milliseconds: 68223.243

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

Answer 1

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.