title: Why python implementation of miller-rabin faster than ruby by a lot?
body: <p>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? </p>
  
  <p>miller_rabin.rb</p>
  
  <pre><code>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
  </code></pre>
  
  <p>miller_rabin.py:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>When I measure the execution time of each using Measure-Command in Windows Powershell, I get the following:</p>
  
  <p>Python 2.7:<br>
  Ticks: 4874403<br>
  Total Milliseconds: 487.4403</p>
  
  <p>Ruby 1.9.3:<br>
  Ticks: 682232430<br>
  Total Milliseconds: 68223.243</p>
  
  <p>I would appreciate any insight anyone can give me into why their is such a huge difference</p>