binary_gcd_algorithm.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 12 August 2017
# https://github.com/trizen

# Algorithm invented by J. Stein in 1967, described in the
# book "Algorithmic Number Theory" by Eric Bach and Jeffrey Shallit.

func binary_gcd(u, v) {

    var g = 1

    while (u.is_even && v.is_even) {
        u >>= 1
        v >>= 1
        g <<= 1
    }

    while (u) {
        if (u.is_even) {
            u >>= 1
        }
        elsif (v.is_even) {
            v >>= 1
        }
        elsif (u >= v) {
            u -= v
            u >>= 1
        }
        else {
            v -= u
            v >>= 1
        }
    }

    return (g * v)
}

say binary_gcd(10628640, 3628800)     #=> 1440
say binary_gcd(3628800,  10628640)    #=> 1440

var u = 484118311800307409686872049018968526148964320406131317406564776592214983358038627898935326228550128722261905040875508300794183477624832000000000000000000000000
var v = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

say binary_gcd(u, v)   #=> 33464469725118339932738475939854523519700805708105926500308251028510111778609255576238987149312000000000000000000000000
say binary_gcd(v, u)   #=> 33464469725118339932738475939854523519700805708105926500308251028510111778609255576238987149312000000000000000000000000