math: improve accuracy of Exp2

Note:
* Exp2 doesn't have a special case for very small arguments
* Exp2 hasn't been subject to a proper error analysis

Also:
* add tests for Exp2 with integer argument
* always test Go versions of Exp and Exp2

R=rsc
CC=Charlie Dorian, PeterGo, golang-dev
https://golang.org/cl/3481041

6 files changed, 238 insertions, 133 deletions

diff --git a/src/pkg/math/Makefile b/src/pkg/math/Makefile
index e0578518e2..71347b7fa1 100644
--- a/src/pkg/math/Makefile
+++ b/src/pkg/math/Makefile
@@ -54,6 +54,7 @@ ALLGOFILES=\
 	copysign.go\
 	erf.go\
 	exp.go\
+	exp_port.go\
 	exp2.go\
 	expm1.go\
 	fabs.go\
diff --git a/src/pkg/math/all_test.go b/src/pkg/math/all_test.go
index 7a612808ff..03d9fe8cda 100644
--- a/src/pkg/math/all_test.go
+++ b/src/pkg/math/all_test.go
@@ -1662,14 +1662,19 @@ func TestErfc(t *testing.T) {
 }
 
 func TestExp(t *testing.T) {
+	testExp(t, Exp, "Exp")
+	testExp(t, ExpGo, "ExpGo")
+}
+
+func testExp(t *testing.T, Exp func(float64) float64, name string) {
 	for i := 0; i < len(vf); i++ {
 		if f := Exp(vf[i]); !close(exp[i], f) {
-			t.Errorf("Exp(%g) = %g, want %g", vf[i], f, exp[i])
+			t.Errorf("%s(%g) = %g, want %g", name, vf[i], f, exp[i])
 		}
 	}
 	for i := 0; i < len(vfexpSC); i++ {
 		if f := Exp(vfexpSC[i]); !alike(expSC[i], f) {
-			t.Errorf("Exp(%g) = %g, want %g", vfexpSC[i], f, expSC[i])
+			t.Errorf("%s(%g) = %g, want %g", name, vfexpSC[i], f, expSC[i])
 		}
 	}
 }
@@ -1689,14 +1694,26 @@ func TestExpm1(t *testing.T) {
 }
 
 func TestExp2(t *testing.T) {
+	testExp2(t, Exp2, "Exp2")
+	testExp2(t, Exp2Go, "Exp2Go")
+}
+
+func testExp2(t *testing.T, Exp2 func(float64) float64, name string) {
 	for i := 0; i < len(vf); i++ {
 		if f := Exp2(vf[i]); !close(exp2[i], f) {
-			t.Errorf("Exp2(%g) = %g, want %g", vf[i], f, exp2[i])
+			t.Errorf("%s(%g) = %g, want %g", name, vf[i], f, exp2[i])
 		}
 	}
 	for i := 0; i < len(vfexpSC); i++ {
 		if f := Exp2(vfexpSC[i]); !alike(expSC[i], f) {
-			t.Errorf("Exp2(%g) = %g, want %g", vfexpSC[i], f, expSC[i])
+			t.Errorf("%s(%g) = %g, want %g", name, vfexpSC[i], f, expSC[i])
+		}
+	}
+	for n := -1074; n < 1024; n++ {
+		f := Exp2(float64(n))
+		vf := Ldexp(1, n)
+		if f != vf {
+			t.Errorf("%s(%d) = %g, want %g", name, n, f, vf)
 		}
 	}
 }
@@ -2352,6 +2369,12 @@ func BenchmarkExp(b *testing.B) {
 	}
 }
 
+func BenchmarkExpGo(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		ExpGo(.5)
+	}
+}
+
 func BenchmarkExpm1(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		Expm1(.5)
@@ -2364,6 +2387,12 @@ func BenchmarkExp2(b *testing.B) {
 	}
 }
 
+func BenchmarkExp2Go(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		Exp2Go(.5)
+	}
+}
+
 func BenchmarkFabs(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		Fabs(.5)
diff --git a/src/pkg/math/exp.go b/src/pkg/math/exp.go
index 90409c341b..c519c2cb6b 100644
--- a/src/pkg/math/exp.go
+++ b/src/pkg/math/exp.go
@@ -4,83 +4,6 @@
 
 package math
 
-
-// The original C code, the long comment, and the constants
-// below are from FreeBSD's /usr/src/lib/msun/src/e_exp.c
-// and came with this notice.  The go code is a simplified
-// version of the original C.
-//
-// ====================================================
-// Copyright (C) 2004 by Sun Microsystems, Inc. All rights reserved.
-//
-// Permission to use, copy, modify, and distribute this
-// software is freely granted, provided that this notice
-// is preserved.
-// ====================================================
-//
-//
-// exp(x)
-// Returns the exponential of x.
-//
-// Method
-//   1. Argument reduction:
-//      Reduce x to an r so that |r| <= 0.5*ln2 ~ 0.34658.
-//      Given x, find r and integer k such that
-//
-//               x = k*ln2 + r,  |r| <= 0.5*ln2.
-//
-//      Here r will be represented as r = hi-lo for better
-//      accuracy.
-//
-//   2. Approximation of exp(r) by a special rational function on
-//      the interval [0,0.34658]:
-//      Write
-//          R(r**2) = r*(exp(r)+1)/(exp(r)-1) = 2 + r*r/6 - r**4/360 + ...
-//      We use a special Remes algorithm on [0,0.34658] to generate
-//      a polynomial of degree 5 to approximate R. The maximum error
-//      of this polynomial approximation is bounded by 2**-59. In
-//      other words,
-//          R(z) ~ 2.0 + P1*z + P2*z**2 + P3*z**3 + P4*z**4 + P5*z**5
-//      (where z=r*r, and the values of P1 to P5 are listed below)
-//      and
-//          |                  5          |     -59
-//          | 2.0+P1*z+...+P5*z   -  R(z) | <= 2
-//          |                             |
-//      The computation of exp(r) thus becomes
-//                             2*r
-//              exp(r) = 1 + -------
-//                            R - r
-//                                 r*R1(r)
-//                     = 1 + r + ----------- (for better accuracy)
-//                                2 - R1(r)
-//      where
-//                               2       4             10
-//              R1(r) = r - (P1*r  + P2*r  + ... + P5*r   ).
-//
-//   3. Scale back to obtain exp(x):
-//      From step 1, we have
-//         exp(x) = 2**k * exp(r)
-//
-// Special cases:
-//      exp(INF) is INF, exp(NaN) is NaN;
-//      exp(-INF) is 0, and
-//      for finite argument, only exp(0)=1 is exact.
-//
-// Accuracy:
-//      according to an error analysis, the error is always less than
-//      1 ulp (unit in the last place).
-//
-// Misc. info.
-//      For IEEE double
-//          if x >  7.09782712893383973096e+02 then exp(x) overflow
-//          if x < -7.45133219101941108420e+02 then exp(x) underflow
-//
-// Constants:
-// The hexadecimal values are the intended ones for the following
-// constants. The decimal values may be used, provided that the
-// compiler will convert from decimal to binary accurately enough
-// to produce the hexadecimal values shown.
-
 // Exp returns e**x, the base-e exponential of x.
 //
 // Special cases are:
@@ -88,54 +11,4 @@ package math
 //	Exp(NaN) = NaN
 // Very large values overflow to 0 or +Inf.
 // Very small values underflow to 1.
-func Exp(x float64) float64 {
-	const (
-		Ln2Hi = 6.93147180369123816490e-01
-		Ln2Lo = 1.90821492927058770002e-10
-		Log2e = 1.44269504088896338700e+00
-		P1    = 1.66666666666666019037e-01  /* 0x3FC55555; 0x5555553E */
-		P2    = -2.77777777770155933842e-03 /* 0xBF66C16C; 0x16BEBD93 */
-		P3    = 6.61375632143793436117e-05  /* 0x3F11566A; 0xAF25DE2C */
-		P4    = -1.65339022054652515390e-06 /* 0xBEBBBD41; 0xC5D26BF1 */
-		P5    = 4.13813679705723846039e-08  /* 0x3E663769; 0x72BEA4D0 */
-
-		Overflow  = 7.09782712893383973096e+02
-		Underflow = -7.45133219101941108420e+02
-		NearZero  = 1.0 / (1 << 28) // 2**-28
-	)
-
-	// TODO(rsc): Remove manual inlining of IsNaN, IsInf
-	// when compiler does it for us
-	// special cases
-	switch {
-	case x != x || x > MaxFloat64: // IsNaN(x) || IsInf(x, 1):
-		return x
-	case x < -MaxFloat64: // IsInf(x, -1):
-		return 0
-	case x > Overflow:
-		return Inf(1)
-	case x < Underflow:
-		return 0
-	case -NearZero < x && x < NearZero:
-		return 1
-	}
-
-	// reduce; computed as r = hi - lo for extra precision.
-	var k int
-	switch {
-	case x < 0:
-		k = int(Log2e*x - 0.5)
-	case x > 0:
-		k = int(Log2e*x + 0.5)
-	}
-	hi := x - float64(k)*Ln2Hi
-	lo := float64(k) * Ln2Lo
-	r := hi - lo
-
-	// compute
-	t := r * r
-	c := r - t*(P1+t*(P2+t*(P3+t*(P4+t*P5))))
-	y := 1 - ((lo - (r*c)/(2-c)) - hi)
-	// TODO(rsc): make sure Ldexp can handle boundary k
-	return Ldexp(y, k)
-}
+func Exp(x float64) float64 { return expGo(x) }
diff --git a/src/pkg/math/exp2.go b/src/pkg/math/exp2.go
index 1e67f29ebc..1cface9d36 100644
--- a/src/pkg/math/exp2.go
+++ b/src/pkg/math/exp2.go
@@ -7,4 +7,4 @@ package math
 // Exp2 returns 2**x, the base-2 exponential of x.
 //
 // Special cases are the same as Exp.
-func Exp2(x float64) float64 { return Exp(x * Ln2) }
+func Exp2(x float64) float64 { return exp2Go(x) }
diff --git a/src/pkg/math/exp_port.go b/src/pkg/math/exp_port.go
new file mode 100644
index 0000000000..071420c24c
--- /dev/null
+++ b/src/pkg/math/exp_port.go
@@ -0,0 +1,192 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package math
+
+
+// The original C code, the long comment, and the constants
+// below are from FreeBSD's /usr/src/lib/msun/src/e_exp.c
+// and came with this notice.  The go code is a simplified
+// version of the original C.
+//
+// ====================================================
+// Copyright (C) 2004 by Sun Microsystems, Inc. All rights reserved.
+//
+// Permission to use, copy, modify, and distribute this
+// software is freely granted, provided that this notice
+// is preserved.
+// ====================================================
+//
+//
+// exp(x)
+// Returns the exponential of x.
+//
+// Method
+//   1. Argument reduction:
+//      Reduce x to an r so that |r| <= 0.5*ln2 ~ 0.34658.
+//      Given x, find r and integer k such that
+//
+//               x = k*ln2 + r,  |r| <= 0.5*ln2.
+//
+//      Here r will be represented as r = hi-lo for better
+//      accuracy.
+//
+//   2. Approximation of exp(r) by a special rational function on
+//      the interval [0,0.34658]:
+//      Write
+//          R(r**2) = r*(exp(r)+1)/(exp(r)-1) = 2 + r*r/6 - r**4/360 + ...
+//      We use a special Remes algorithm on [0,0.34658] to generate
+//      a polynomial of degree 5 to approximate R. The maximum error
+//      of this polynomial approximation is bounded by 2**-59. In
+//      other words,
+//          R(z) ~ 2.0 + P1*z + P2*z**2 + P3*z**3 + P4*z**4 + P5*z**5
+//      (where z=r*r, and the values of P1 to P5 are listed below)
+//      and
+//          |                  5          |     -59
+//          | 2.0+P1*z+...+P5*z   -  R(z) | <= 2
+//          |                             |
+//      The computation of exp(r) thus becomes
+//                             2*r
+//              exp(r) = 1 + -------
+//                            R - r
+//                                 r*R1(r)
+//                     = 1 + r + ----------- (for better accuracy)
+//                                2 - R1(r)
+//      where
+//                               2       4             10
+//              R1(r) = r - (P1*r  + P2*r  + ... + P5*r   ).
+//
+//   3. Scale back to obtain exp(x):
+//      From step 1, we have
+//         exp(x) = 2**k * exp(r)
+//
+// Special cases:
+//      exp(INF) is INF, exp(NaN) is NaN;
+//      exp(-INF) is 0, and
+//      for finite argument, only exp(0)=1 is exact.
+//
+// Accuracy:
+//      according to an error analysis, the error is always less than
+//      1 ulp (unit in the last place).
+//
+// Misc. info.
+//      For IEEE double
+//          if x >  7.09782712893383973096e+02 then exp(x) overflow
+//          if x < -7.45133219101941108420e+02 then exp(x) underflow
+//
+// Constants:
+// The hexadecimal values are the intended ones for the following
+// constants. The decimal values may be used, provided that the
+// compiler will convert from decimal to binary accurately enough
+// to produce the hexadecimal values shown.
+
+// Exp returns e**x, the base-e exponential of x.
+//
+// Special cases are:
+//	Exp(+Inf) = +Inf
+//	Exp(NaN) = NaN
+// Very large values overflow to 0 or +Inf.
+// Very small values underflow to 1.
+func expGo(x float64) float64 {
+	const (
+		Ln2Hi = 6.93147180369123816490e-01
+		Ln2Lo = 1.90821492927058770002e-10
+		Log2e = 1.44269504088896338700e+00
+
+		Overflow  = 7.09782712893383973096e+02
+		Underflow = -7.45133219101941108420e+02
+		NearZero  = 1.0 / (1 << 28) // 2**-28
+	)
+
+	// TODO(rsc): Remove manual inlining of IsNaN, IsInf
+	// when compiler does it for us
+	// special cases
+	switch {
+	case x != x || x > MaxFloat64: // IsNaN(x) || IsInf(x, 1):
+		return x
+	case x < -MaxFloat64: // IsInf(x, -1):
+		return 0
+	case x > Overflow:
+		return Inf(1)
+	case x < Underflow:
+		return 0
+	case -NearZero < x && x < NearZero:
+		return 1 + x
+	}
+
+	// reduce; computed as r = hi - lo for extra precision.
+	var k int
+	switch {
+	case x < 0:
+		k = int(Log2e*x - 0.5)
+	case x > 0:
+		k = int(Log2e*x + 0.5)
+	}
+	hi := x - float64(k)*Ln2Hi
+	lo := float64(k) * Ln2Lo
+
+	// compute
+	return exp(hi, lo, k)
+}
+
+// Exp2 returns 2**x, the base-2 exponential of x.
+//
+// Special cases are the same as Exp.
+func exp2Go(x float64) float64 {
+	const (
+		Ln2Hi = 6.93147180369123816490e-01
+		Ln2Lo = 1.90821492927058770002e-10
+
+		Overflow  = 1.0239999999999999e+03
+		Underflow = -1.0740e+03
+	)
+
+	// TODO: remove manual inlining of IsNaN and IsInf
+	// when compiler does it for us
+	// special cases
+	switch {
+	case x != x || x > MaxFloat64: // IsNaN(x) || IsInf(x, 1):
+		return x
+	case x < -MaxFloat64: // IsInf(x, -1):
+		return 0
+	case x > Overflow:
+		return Inf(1)
+	case x < Underflow:
+		return 0
+	}
+
+	// argument reduction; x = r×lg(e) + k with |r| ≤ ln(2)/2.
+	// computed as r = hi - lo for extra precision.
+	var k int
+	switch {
+	case x > 0:
+		k = int(x + 0.5)
+	case x < 0:
+		k = int(x - 0.5)
+	}
+	t := x - float64(k)
+	hi := t * Ln2Hi
+	lo := -t * Ln2Lo
+
+	// compute
+	return exp(hi, lo, k)
+}
+
+// exp returns e**r × 2**k where r = hi - lo and |r| ≤ ln(2)/2.
+func exp(hi, lo float64, k int) float64 {
+	const (
+		P1 = 1.66666666666666019037e-01  /* 0x3FC55555; 0x5555553E */
+		P2 = -2.77777777770155933842e-03 /* 0xBF66C16C; 0x16BEBD93 */
+		P3 = 6.61375632143793436117e-05  /* 0x3F11566A; 0xAF25DE2C */
+		P4 = -1.65339022054652515390e-06 /* 0xBEBBBD41; 0xC5D26BF1 */
+		P5 = 4.13813679705723846039e-08  /* 0x3E663769; 0x72BEA4D0 */
+	)
+
+	r := hi - lo
+	t := r * r
+	c := r - t*(P1+t*(P2+t*(P3+t*(P4+t*P5))))
+	y := 1 - ((lo - (r*c)/(2-c)) - hi)
+	// TODO(rsc): make sure Ldexp can handle boundary k
+	return Ldexp(y, k)
+}
diff --git a/src/pkg/math/exp_test.go b/src/pkg/math/exp_test.go
new file mode 100644
index 0000000000..7381fd5ad3
--- /dev/null
+++ b/src/pkg/math/exp_test.go
@@ -0,0 +1,10 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package math
+
+// Make expGo and exp2Go available for testing.
+
+func ExpGo(x float64) float64  { return expGo(x) }
+func Exp2Go(x float64) float64 { return exp2Go(x) }