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")
	}
}

LANGUAGE:

DARK MODE: