math/big: optimize multiplication by 2 and 1/2 in float Sqrt

The Sqrt code previously used explicit constants for 2 and 1/2.  This change
replaces multiplication by these constants with increment and decrement of
the floating point exponent directly.  This improves performance by ~7-10%
for small inputs and minimal improvement for large inputs.

name                 old time/op    new time/op    delta
FloatSqrt/64-4         1.39µs ± 0%    1.29µs ± 3%   -7.01%  (p=0.016 n=4+5)
FloatSqrt/128-4        2.84µs ± 0%    2.60µs ± 1%   -8.33%  (p=0.008 n=5+5)
FloatSqrt/256-4        3.24µs ± 1%    2.91µs ± 2%  -10.00%  (p=0.008 n=5+5)
FloatSqrt/1000-4       7.42µs ± 1%    6.74µs ± 0%   -9.16%  (p=0.008 n=5+5)
FloatSqrt/10000-4      65.9µs ± 1%    65.3µs ± 4%     ~     (p=0.310 n=5+5)
FloatSqrt/100000-4     1.57ms ± 8%    1.52ms ± 1%     ~     (p=0.111 n=5+4)
FloatSqrt/1000000-4     127ms ± 1%     126ms ± 1%     ~     (p=0.690 n=5+5)

Change-Id: Id81ac842a9d64981e001c4ca3ff129eebd227593
Reviewed-on: https://go-review.googlesource.com/130835
Reviewed-by: Robert Griesemer <gri@golang.org>

1 files changed, 10 insertions, 10 deletions

diff --git a/src/math/big/sqrt.go b/src/math/big/sqrt.go
index b989649dcd..53403aa41d 100644
--- a/src/math/big/sqrt.go
+++ b/src/math/big/sqrt.go
@@ -7,8 +7,6 @@ package big
 import "math"
 
 var (
-	half  = NewFloat(0.5)
-	two   = NewFloat(2.0)
 	three = NewFloat(3.0)
 )
 
@@ -57,9 +55,9 @@ func (z *Float) Sqrt(x *Float) *Float {
 	case 0:
 		// nothing to do
 	case 1:
-		z.Mul(two, z)
+		z.exp++
 	case -1:
-		z.Mul(half, z)
+		z.exp--
 	}
 	// 0.25 <= z < 2.0
 
@@ -96,7 +94,7 @@ func (z *Float) sqrtDirect(x *Float) {
 		u.prec = t.prec
 		u.Mul(t, t)        // u = t²
 		u.Add(u, x)        //   = t² + x
-		u.Mul(half, u)     //   = ½(t² + x)
+		u.exp--            //   = ½(t² + x)
 		return t.Quo(u, t) //   = ½(t² + x)/t
 	}
 
@@ -133,11 +131,13 @@ func (z *Float) sqrtInverse(x *Float) {
 	ng := func(t *Float) *Float {
 		u.prec = t.prec
 		v.prec = t.prec
-		u.Mul(t, t)           // u = t²
-		u.Mul(x, u)           //   = xt²
-		v.Sub(three, u)       // v = 3 - xt²
-		u.Mul(t, v)           // u = t(3 - xt²)
-		return t.Mul(half, u) //   = ½t(3 - xt²)
+		u.Mul(t, t)     // u = t²
+		u.Mul(x, u)     //   = xt²
+		v.Sub(three, u) // v = 3 - xt²
+		u.Mul(t, v)     // u = t(3 - xt²)
+		u.exp--         //   = ½t(3 - xt²)
+		return t.Set(u)
+
 	}
 
 	xf, _ := x.Float64()