TL;DR

I read about Stein’s algorithm for calculating the greatest common divisor between two integers. Interesting.

So it seems that finding the greatest common divisor is a hot topic in this blog, considering that I already wrote about it in The extended Euclid’s algorithm. Go figure.

The algorithm is rooted in a few equivalences, which are fine. The most challenging might be considered the last one, i.e.:

$g = gcd(u, v) = gcd(|u − v|, min(u, v))$ if $u$ and $v$ are both odd.

When you think about it, anyway, it’s pretty obvious: an integer $g$ that divides both $u$ and $v$ must also divide their difference and its absolute value. The contrary also applies, which accounts for reading the equivalence in the reverse direction.

Here’s a possible iterative implementation (you know I’m fond of them):

sub stein ($u, $v) {
   die 'the greatest common divisor for (0, 0) is undefined)'
      unless $u || $v;

   # cope with edge cases, insist on using positive integers only
   $u = -$u if $u < 0;
   return $u unless $v;
   $v = -$v if $v < 0;
   return $v unless $u;

   # we have to go into the rabbit hole here...
   my $retval = 1;

   # first phase, find out the contributing power of 2, if any
   while (($u % 2 == 0) && ($v % 2 == 0)) {
      $retval <<= 1;
      $v >>= 1;
      $u >>= 1;
   }

   # second phase, from now on either u and v will be odd
   while ('necessary') {
      $v >>= 1 while $v % 2 == 0; # we don't need evens here
      $u >>= 1 while $u % 2 == 0; # ditto
      return $retval * $u if $v == $u;
      ($u, $v) = $u < $v ? ($v - $u, $u) : ($u - $v, $v);
   }
}

Aside question: why $u$ and $v$ instead of $n$ and $m$? I guess it was a personal preference of Stein…