緣起
最近閱讀<<我的第一本算法書>>(【日】石田保輝；宮崎修一)
本系列筆記擬采用golang練習(xí)之
歐幾里得算法
歐幾里得算法（又稱輾轉(zhuǎn)相除法）用于計算兩個數(shù)的最大公約數(shù)，
被稱為世界上最古老的算法。
現(xiàn)在人們已無法確定該算法具體的提出時間，
但其最早被發(fā)現(xiàn)記載于公元前300年歐幾里得的著作中，
因此得以命名。
首先用較小的數(shù)字去除較大的數(shù)字，求出余數(shù)。
接下來再用較小的除數(shù)和余數(shù)進行mod運算,
重復(fù)同樣的操作,
余數(shù)為0時，最后一次運算中的除數(shù)就是最大公約數(shù)。
摘自 <<我的第一本算法書>> 【日】石田保輝；宮崎修一
Euclidean-algorithm.jpg
目標
- 分別用因式分解法和歐幾里德算法求解若干隨機整數(shù)的最大公約數(shù), 并相互驗證
設(shè)計
- IGCDCalculator: 最大公約數(shù)計算器接口
- tEuclideanCalculator: 歐幾里德算法實現(xiàn)最大公約數(shù)求解
- tNormalGcdCalculator: 因式分解法實現(xiàn)最大公約數(shù)求解
單元測試
euclidean_gcd_test.go, 對比驗證歐幾里德算法和因式分解法, 并比較計算效率
package others
import (
"learning/gooop/others/euclidean"
"math/rand"
"testing"
"time"
)
func TestEuclideanGCD(t *testing.T) {
fnAssertTrue := func(b bool, msg string) {
if !b {
t.Fatal(msg)
}
}
rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
sampleCount := 100
samples := make([]int, sampleCount)
for i,_ := range samples {
samples[i] = rnd.Intn(sampleCount) + 1
}
fnGenInt := func() int {
n := rnd.Intn(5) + 1
x := 1
for i := 0;i < n;i++ {
j := rnd.Intn(sampleCount)
x *= samples[j]
}
return x
}
c1 := euclidean.EuclideanGCDCalculator
c2 := euclidean.NormalGCDCalculator
t.Log("testing 10 samples")
for i := 0;i < 10;i++ {
a,b := fnGenInt(), fnGenInt()
g1 := c1.Calc(a, b)
g2 := c2.Calc(a, b)
//t.Logf("a=%v, b=%v, g1=%v, g2=%v", a, b, g1, g2)
fnAssertTrue(g1 == g2, "expecting g1 == g2")
fnAssertTrue(a % g1 == 0, "expecting a % gcd == 0")
fnAssertTrue(b % g1 == 0, "expecting b % gcd == 0")
t.Logf("gcd(%v, %v) = %v", a, b, g1)
}
t.Log("pass testing 10 samples")
t.Log("\ntesting 100_000 samples")
for i := 0;i < 100_000;i++ {
a,b := fnGenInt(), fnGenInt()
g1 := c1.Calc(a, b)
g2 := c2.Calc(a, b)
fnAssertTrue(g1 == g2, "expecting g1 == g2")
fnAssertTrue(a % g1 == 0, "expecting a % gcd == 0")
fnAssertTrue(b % g1 == 0, "expecting b % gcd == 0")
}
t.Log("pass testing 100_000 samples")
fnTestCost := func(samples[][] int, c euclidean.IGCDCalculator) int64 {
t0 := time.Now().UnixNano()
for i, size := 0, len(samples);i < size;i++ {
a, b := samples[i][0], samples[i][1]
g1 := c.Calc(a, b)
fnAssertTrue(a%g1 == 0, "expecting a % gcd == 0")
fnAssertTrue(b%g1 == 0, "expecting b % gcd == 0")
}
cost := (time.Now().UnixNano() - t0) / 1000_000
return cost
}
pairs := make([][]int, 10_000)
for i,size := 0, len(pairs);i < size;i++ {
pairs[i] = []int{ fnGenInt(), fnGenInt() }
}
t.Logf("testing 10_000 samples using EuclideanGCDCalculator, cost=%v ms", fnTestCost(pairs, c1))
t.Logf("testing 10_000 samples using NormalGCDCalculator, cost=%v ms", fnTestCost(pairs, c2))
}
測試輸出
顯而易見, 歐幾里德算法要快上N個數(shù)量級
$ go test -v euclidean_gcd_test.go
=== RUN TestEuclideanGCD
euclidean_gcd_test.go:37: testing 10 samples
euclidean_gcd_test.go:47: gcd(122262, 2135280) = 1722
euclidean_gcd_test.go:47: gcd(2563600, 180180) = 260
euclidean_gcd_test.go:47: gcd(5, 2019600) = 5
euclidean_gcd_test.go:47: gcd(78540, 1547) = 119
euclidean_gcd_test.go:47: gcd(17476560, 749800800) = 563760
euclidean_gcd_test.go:47: gcd(395600, 12792) = 8
euclidean_gcd_test.go:47: gcd(21, 165) = 3
euclidean_gcd_test.go:47: gcd(7056, 2257) = 1
euclidean_gcd_test.go:47: gcd(90, 918) = 18
euclidean_gcd_test.go:47: gcd(90843648, 2522520) = 1176
euclidean_gcd_test.go:49: pass testing 10 samples
euclidean_gcd_test.go:51:
testing 100_000 samples
euclidean_gcd_test.go:61: pass testing 100_000 samples
euclidean_gcd_test.go:80: testing 10_000 samples using EuclideanGCDCalculator, cost=1 ms
euclidean_gcd_test.go:81: testing 10_000 samples using NormalGCDCalculator, cost=721 ms
--- PASS: TestEuclideanGCD (8.34s)
PASS
ok command-line-arguments 8.347s
IGCDCalculator.go
最大公約數(shù)計算器接口
package euclidean
type IGCDCalculator interface {
Calc(a, b int) int
}
tEuclideanCalculator.go
歐幾里德算法實現(xiàn)最大公約數(shù)求解
package euclidean
type tEuclideanCalculator struct {
}
func newEuclideanCalculator() IGCDCalculator {
return &tEuclideanCalculator{}
}
func (me *tEuclideanCalculator) Calc(a, b int) int {
if a <= 0 || b <= 0 {
return 1
}
if a == b {
return a
}
bigger := max(a, b)
smaller := min(a, b)
for smaller > 0 {
remaining := bigger % smaller
if remaining == 0 {
return smaller
} else {
bigger ,smaller = smaller, remaining
}
}
return 1
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
func min(a, b int) int {
if a <= b {
return a
}
return b
}
var EuclideanGCDCalculator = newEuclideanCalculator()
tNormalGcdCalculator.go
因式分解法實現(xiàn)最大公約數(shù)求解
package euclidean
import (
"math"
"sort"
)
type tNormalGcdCalculator struct {
}
func newNormalGcdCalculator() IGCDCalculator {
return &tNormalGcdCalculator{}
}
func (me *tNormalGcdCalculator) Calc(a, b int) int {
if a <= 0 || b <= 0 {
return 1
}
if a == b {
return a
}
aa := me.split(a)
sort.Sort(sort.IntSlice(aa))
bb := me.split(b)
sort.Sort(sort.IntSlice(bb))
for i, j := len(aa) - 1, len(bb) - 1;i >= 0 && j >= 0; {
if aa[i] == bb[j] {
return aa[i]
}
if aa[i] > bb[j] {
i--
} else {
j--
}
}
return 1
}
func (me *tNormalGcdCalculator) split(a int) []int {
to := int(math.Floor(math.Sqrt(float64(a))))
items := make([]int, 0)
for i := 1;i <= to;i++ {
if a % i == 0 {
items = append(items, i)
items = append(items, a / i)
}
}
return items
}
var NormalGCDCalculator = newNormalGcdCalculator()
(end)
