gcd Algorithm
In arithmetical and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, normally denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero.
package gcd
import "testing"
func gcd(x uint, y uint) uint {
var shift uint = 0
if x == y {
return x
}
if x == 0 {
return y
}
if y == 0 {
return x
}
for shift := 0; (x | y) & 1 == 0; shift++ {
x = x >> 1
y = y >> 1
}
for ; (x & 1) == 0 ; {
x = x >> 1
}
for ; y == 0 ; {
for ; (y & 1) == 0 ; {
y = y >> 1
}
if x > y {
t := x
x = y
y = t
}
y = y - x
}
y = y << shift
return y
}
func Test_gcd(t *testing.T) {
if gcd(100, 200) != 50 {
t.Error("[Error] gcd(100, 200) is wrong")
}
if gcd(4, 2) != 1 {
t.Error("[Error] gcd(4,2) is wrong")
}
if gcd(6, 3) != 3 {
t.Error("[Error] gcd(6,3) is wrong")
}
}