GCD

gcd.go

package gcd

import "fmt"
import "math/big"

func Dedup(l []int64) []int64 {
	list := make([]int64, len(l))
	copy(list, l)

	last := len(list) - 1
	for x := 0; x <= last; x++ {
		for y := x + 1; y <= last; y++ {
			if list[y] == list[x] {
				list[y] = list[last]
				list = list[:last]
				last--
				y--
			}
		}
	}

	return list
}

func Gcd(a int64, b int64) int64 {
	A := big.NewInt(a)
	B := big.NewInt(b)
	I := &big.Int{}

	return I.GCD(nil, nil, A, B).Int64()
}

func GcdOfMany(list ...int64) (int64, error) {
	if len(list) == 0 {
		return 0, fmt.Errorf("Empty list")
	}

	uniq := Dedup(list)
	if len(uniq) == 1 {
		return uniq[0], nil
	}

	var next []int64
	for i := 1; i < len(uniq); i = i + 2 {
		next = append(next, Gcd(uniq[i], uniq[i-1]))
	}

	return GcdOfMany(next...)
}