math/big: Implemented binary GCD algorithm

benchmark                    old ns/op    new ns/op    delta
BenchmarkGCD10x10                 4383         2126  -51.49%
BenchmarkGCD10x100                5612         2124  -62.15%
BenchmarkGCD10x1000               8843         2622  -70.35%
BenchmarkGCD10x10000             17025         6576  -61.37%
BenchmarkGCD10x100000           118985        48130  -59.55%
BenchmarkGCD100x100              45328        11683  -74.23%
BenchmarkGCD100x1000             50141        12678  -74.72%
BenchmarkGCD100x10000           110314        26719  -75.78%
BenchmarkGCD100x100000          630000       156041  -75.23%
BenchmarkGCD1000x1000           654809       137973  -78.93%
BenchmarkGCD1000x10000          985683       159951  -83.77%
BenchmarkGCD1000x100000        4920792       366399  -92.55%
BenchmarkGCD10000x10000       16848950      3732062  -77.85%
BenchmarkGCD10000x100000      55401500      4675876  -91.56%
BenchmarkGCD100000x100000   1126775000    258951800  -77.02%

R=gri, rsc, bradfitz, remyoudompheng, mtj
CC=golang-dev
http://codereview.appspot.com/6305065

Committer: Robert Griesemer <gri@golang.org>

1 files changed, 7 insertions, 17 deletions

diff --git a/src/pkg/math/big/rat.go b/src/pkg/math/big/rat.go
index 5c2a48654..eccf34e48 100644
--- a/src/pkg/math/big/rat.go
+++ b/src/pkg/math/big/rat.go
@@ -145,20 +145,6 @@ func (x *Rat) Denom() *Int {
 	return &x.b
 }
 
-func gcd(x, y nat) nat {
-	// Euclidean algorithm.
-	var a, b nat
-	a = a.set(x)
-	b = b.set(y)
-	for len(b) != 0 {
-		var q, r nat
-		_, r = q.div(r, a, b)
-		a = b
-		b = r
-	}
-	return a
-}
-
 func (z *Rat) norm() *Rat {
 	switch {
 	case len(z.a.abs) == 0:
@@ -171,14 +157,18 @@ func (z *Rat) norm() *Rat {
 		// z is int - normalize denominator
 		z.b.abs = z.b.abs.make(0)
 	default:
-		if f := gcd(z.a.abs, z.b.abs); f.cmp(natOne) != 0 {
-			z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f)
-			z.b.abs, _ = z.b.abs.div(nil, z.b.abs, f)
+		neg := z.a.neg
+		z.a.neg = false
+		z.b.neg = false
+		if f := NewInt(0).binaryGCD(&z.a, &z.b); f.Cmp(intOne) != 0 {
+			z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f.abs)
+			z.b.abs, _ = z.b.abs.div(nil, z.b.abs, f.abs)
 			if z.b.abs.cmp(natOne) == 0 {
 				// z is int - normalize denominator
 				z.b.abs = z.b.abs.make(0)
 			}
 		}
+		z.a.neg = neg
 	}
 	return z
 }