From 133cdb6707ba88f83746db1efd15c4cb3034ff62 Mon Sep 17 00:00:00 2001 From: Adam Langley Date: Wed, 15 May 2013 10:03:22 -0400 Subject: [PATCH] math/big: save some copies in binaryGCD. This patch resulted from a bit of quick optimisation in response to a golang-nuts post. It looks like one could save a couple other copies in this function, but this addresses the inner loop and is fairly simple. benchmark old ns/op new ns/op delta BenchmarkGCD10x10 1964 1711 -12.88% BenchmarkGCD10x100 2019 1736 -14.02% BenchmarkGCD10x1000 2471 2171 -12.14% BenchmarkGCD10x10000 6040 5778 -4.34% BenchmarkGCD10x100000 43204 43025 -0.41% BenchmarkGCD100x100 11004 8520 -22.57% BenchmarkGCD100x1000 11820 9446 -20.08% BenchmarkGCD100x10000 23846 21382 -10.33% BenchmarkGCD100x100000 133691 131505 -1.64% BenchmarkGCD1000x1000 120041 95591 -20.37% BenchmarkGCD1000x10000 136887 113600 -17.01% BenchmarkGCD1000x100000 295370 273912 -7.26% BenchmarkGCD10000x10000 2556126 2205198 -13.73% BenchmarkGCD10000x100000 3159512 2808038 -11.12% BenchmarkGCD100000x100000 150543094 139986045 -7.01% R=gri, remyoudompheng CC=bradfitz, gobot, golang-dev, gri https://golang.org/cl/9424043 --- src/pkg/math/big/int.go | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/src/pkg/math/big/int.go b/src/pkg/math/big/int.go index d1b5602d66..09051f82ed 100644 --- a/src/pkg/math/big/int.go +++ b/src/pkg/math/big/int.go @@ -703,14 +703,15 @@ func (z *Int) binaryGCD(a, b *Int) *Int { // reduce t t.Rsh(t, t.abs.trailingZeroBits()) if t.neg { - v.Neg(t) + v, t = t, v + v.neg = len(v.abs) > 0 && !v.neg // 0 has no sign } else { - u.Set(t) + u, t = t, u } t.Sub(u, v) } - return u.Lsh(u, k) + return z.Lsh(u, k) } // ProbablyPrime performs n Miller-Rabin tests to check whether x is prime. -- 2.48.1