Binary GCD for Golang

gcd.go

package gcd

// GCD binary algorithm, derived from
// https://en.wikipedia.org/wiki/Binary_GCD_algorithm#Iterative_version_in_C
func GCD(u, v uint64) uint64 {
	var shift uint

	/* GCD(0,v) == v; GCD(u,0) == u, GCD(0,0) == 0 */
	if u == 0 {
		return v
	}
	if v == 0 {
		return u
	}

	/* Let shift := lg K, where K is the greatest power of 2
	   dividing both u and v. */
	for shift = 0; ((u | v) & 1) == 0; shift++ {
		u >>= 1
		v >>= 1
	}

	// While u is even, continue dividing by 2 (right-shift) until it becomes odd
	for (u & 1) == 0 {
		u >>= 1
	}

	/* From here on, u is always odd. */
	for ok := true; ok; ok = (v != 0) {
		/* remove all factors of 2 in v -- they are not common */
		/*   note: v is not zero, so while will terminate */
		for (v & 1) == 0 /* Loop X */ {
			v >>= 1
		}

		/* Now u and v are both odd. Swap if necessary so u <= v,
		   then set v = v - u (which is even). For bignums, the
		   swapping is just pointer movement, and the subtraction
		   can be done in-place. */
		if u > v {
			// Swap u and v.
			//  unsigned int t = v; v = u; u = t;}
			v, u = u, v
		}
		v = v - u // Here v >= u.
	}

	/* restore common factors of 2 */
	return u << shift
}

gcd_test.go

package gcd

import (
	"math/big"
	"testing"
	"testing/quick"
)

func TestGCD(t *testing.T) {
	f := func(u, v uint8) bool {
		if u == 0 || v == 0 {
			return true
		}
		result := GCD(uint64(u), uint64(v))

		bigU := big.NewInt(int64(u))
		bigV := big.NewInt(int64(v))
		bigU.GCD(nil, nil, bigU, bigV)

		ok := bigU.Int64() == int64(result)
		if !ok {
			t.Logf("we got %d, they got %d", result, bigU.Int64())
		}
		return ok
	}

	err := quick.Check(f, &quick.Config{})
	if err != nil {
		t.Fatal(err)
	}
}

func BenchmarkBigGCD(b *testing.B) {
	for i := 0; i < b.N; i++ {
		u := big.NewInt(int64(i * 2))
		v := big.NewInt(int64(i * 3))
		u.GCD(nil, nil, u, v)
	}
}

// BenchmarkBigGCD-4        3000000               467 ns/op             320 B/op          8 allocs/op
// BenchmarkBinaryGCD-4    100000000               12.2 ns/op             0 B/op          0 allocs/op
func BenchmarkBinaryGCD(b *testing.B) {
	for i := 0; i < b.N; i++ {
		u := uint64(i * 2)
		v := uint64(i * 3)
		math.GCD(u, v)
	}
}