stein_gcd

The binary GCD algorithm, also known as Stein's algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction.

function stein_gcd(a, b)
{
    //Logic
    if(a == 0) return b;
    if(b == 0) return a;
    var k;
    for(k = 0; ((a | b) && 1) == 0; ++k)
    {
      a >>= 1;
      b >>= 1;
    }
    while((a > 1) == 0) a >>= 1;
    do
    {
      while((b > 1) == 0) b >>= 1;
      if (a > b)
      {
        var t = a;
        a = b;
        b = t;
      }
      b = (b - a);
    } while(b != 0);
    return a << k;
}