Why is the binary GCD algorithm so much slower for me?

Question

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

According to Wikipedia it's supposed to be a wee bit faster than Euclid's algorithm (not much, but I was at least expecting to get equal performance). For me it is an order of magnitude slower. Could you guys help me figure out why?

I tried implementing it in Ruby. First I went with a recursive solution

def gcd_recursive(u, v)
return u|v if u==0 or v==0

if u.even?
  if v.even?
    return gcd(u>>1, v>>1)<<1
  else
    return gcd(u>>1, v) if v.odd?
  end
elsif u.odd? and v.even?
  return gcd(u, v>>1)
else
  if u < v
    u, v = v, u
  end
  return gcd((u-v)>>1, v)
end
end

That didn't work that well, so I wanted to check how fast it would be if it was a loop

def gcd(u, v)
  return u|v if u==0 or v==0
  shift=0
  while ((u|v)&1)==0 do
    u=u >> 1;
    v=v >> 1;
    shift += 1
  end
  while ((u&1) == 0) do 
    u=u >> 1
  end
  begin
    while ((v & 1) == 0) do
      v=v >> 1
    end

    if u < v
      v -= u
    else
      diff = u - v
      u = v
      v = diff
    end
  end while v != 0
  u<<shift
end

These are the benchmark results

       user     system      total        real
std  0.300000   0.000000   0.300000 (  0.313091)
rbn  0.850000   0.000000   0.850000 (  0.872319)
bin  2.730000   0.000000   2.730000 (  2.782937)
rec  3.070000   0.000000   3.070000 (  3.136301)

std is the native ruby 1.9.3 C implementation.

rbn is basically the same thing (Euclid's algorithm), but written in Ruby.

bin is the loop code you see above.

rec is the recursive version.

EDIT: I ran the benchmark up there on matz' ruby 1.9.3. I tried running the same test on Rubinius and this is what I got. This is also confusing...

 rbn  1.268079   0.024001   1.292080 (  1.585107)
 bin  1.300082   0.000000   1.300082 (  1.775378)
 rec  1.396087   0.000000   1.396087 (  2.348785)

Answer 1

This is just a guess, but I suspect it's a combination of two reasons:

1. The binary GCD algorithm is more complex than Euclid's algorithm, and involves lower-level operations, so it suffers more from interpretation overhead when implemented in a high-level language like Ruby.
2. Modern computers tend to have fast division (and modulo) instructions, making the standard Euclidean algorithm hard to compete with.