From 8c6643846ef5572cb138c8f7c9ac2b1b3cb1d06c Mon Sep 17 00:00:00 2001 From: =?utf8?q?Martin=20M=C3=B6hrmann?= Date: Sat, 10 Dec 2016 08:04:40 +0100 Subject: [PATCH] math: speed up and improve accuracy of Pow10 MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Removes init function from the math package. Allows stripping of arrays with pre-computed values used for Pow10 from binaries if Pow10 is not used. cmd/go shrinks by 128 bytes. Fixed small values like 10**-323 being 0 instead of 1e-323. Overall precision is increased but still not as good as predefined constants for some inputs. Samples: Pow10(208) before: 1.0000000000000006662e+208 after: 1.0000000000000000959e+208 Pow10(202) before 1.0000000000000009895e+202 after 1.0000000000000001193e+202 Pow10(60) before 1.0000000000000001278e+60 after 0.9999999999999999494e+60 Pow10(-100) before 0.99999999999999938551e-100 after 0.99999999999999989309e-100 Pow10(-200) before 0.9999999999999988218e-200 after 1.0000000000000001271e-200 name old time/op new time/op delta Pow10Pos-4 44.6ns ± 2% 1.2ns ± 1% -97.39% (p=0.000 n=19+17) Pow10Neg-4 50.8ns ± 1% 4.1ns ± 2% -92.02% (p=0.000 n=17+19) Change-Id: If094034286b8ac64be3a95fd9e8ffa3d4ad39b31 Reviewed-on: https://go-review.googlesource.com/36331 Reviewed-by: Robert Griesemer Run-TryBot: Martin Möhrmann TryBot-Result: Gobot Gobot --- src/math/all_test.go | 42 ++++++++++++++++++++++++++------- src/math/pow10.go | 56 ++++++++++++++++++++++++-------------------- 2 files changed, 65 insertions(+), 33 deletions(-) diff --git a/src/math/all_test.go b/src/math/all_test.go index 967849c036..39a3a4986b 100644 --- a/src/math/all_test.go +++ b/src/math/all_test.go @@ -1646,16 +1646,38 @@ var powSC = []float64{ var vfpow10SC = []int{ MinInt32, - MaxInt32, - -325, + -324, + -323, + -50, + -22, + -1, + 0, + 1, + 22, + 50, + 100, + 200, + 308, 309, + MaxInt32, } var pow10SC = []float64{ - 0, // pow10(MinInt32) - Inf(1), // pow10(MaxInt32) - 0, // pow10(-325) - Inf(1), // pow10(309) + 0, // pow10(MinInt32) + 0, // pow10(-324) + 1.0e-323, // pow10(-323) + 1.0e-50, // pow10(-50) + 1.0e-22, // pow10(-22) + 1.0e-1, // pow10(-1) + 1.0e0, // pow10(0) + 1.0e1, // pow10(1) + 1.0e22, // pow10(22) + 1.0e50, // pow10(50) + 1.0e100, // pow10(100) + 1.0e200, // pow10(200) + 1.0e308, // pow10(308) + Inf(1), // pow10(309) + Inf(1), // pow10(MaxInt32) } var vfsignbitSC = []float64{ @@ -3179,18 +3201,22 @@ func BenchmarkPowFrac(b *testing.B) { GlobalF = x } +var pow10pos = int(300) + func BenchmarkPow10Pos(b *testing.B) { x := 0.0 for i := 0; i < b.N; i++ { - x = Pow10(300) + x = Pow10(pow10pos) } GlobalF = x } +var pow10neg = int(-300) + func BenchmarkPow10Neg(b *testing.B) { x := 0.0 for i := 0; i < b.N; i++ { - x = Pow10(-300) + x = Pow10(pow10neg) } GlobalF = x } diff --git a/src/math/pow10.go b/src/math/pow10.go index f5ad28bb4b..1234e20885 100644 --- a/src/math/pow10.go +++ b/src/math/pow10.go @@ -4,37 +4,43 @@ package math -// This table might overflow 127-bit exponent representations. -// In that case, truncate it after 1.0e38. -var pow10tab [70]float64 +// pow10tab stores the pre-computed values 10**i for i < 32. +var pow10tab = [...]float64{ + 1e00, 1e01, 1e02, 1e03, 1e04, 1e05, 1e06, 1e07, 1e08, 1e09, + 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, + 1e20, 1e21, 1e22, 1e23, 1e24, 1e25, 1e26, 1e27, 1e28, 1e29, + 1e30, 1e31, +} + +// pow10postab32 stores the pre-computed value for 10**(i*32) at index i. +var pow10postab32 = [...]float64{ + 1e00, 1e32, 1e64, 1e96, 1e128, 1e160, 1e192, 1e224, 1e256, 1e288, +} + +// pow10negtab32 stores the pre-computed value for 10**(-i*32) at index i. +var pow10negtab32 = [...]float64{ + 1e-00, 1e-32, 1e-64, 1e-96, 1e-128, 1e-160, 1e-192, 1e-224, 1e-256, 1e-288, 1e-320, +} -// Pow10 returns 10**e, the base-10 exponential of e. +// Pow10 returns 10**n, the base-10 exponential of n. // // Special cases are: -// Pow10(e) = +Inf for e > 309 -// Pow10(e) = 0 for e < -324 -func Pow10(e int) float64 { - if e <= -325 { - return 0 - } else if e > 309 { - return Inf(1) +// Pow10(n) = 0 for n < -323 +// Pow10(n) = +Inf for n > 308 +func Pow10(n int) float64 { + if 0 <= n && n <= 308 { + return pow10postab32[uint(n)/32] * pow10tab[uint(n)%32] } - if e < 0 { - return 1 / Pow10(-e) - } - if e < len(pow10tab) { - return pow10tab[e] + if -323 <= n && n <= 0 { + return pow10negtab32[uint(-n)/32] / pow10tab[uint(-n)%32] } - m := e / 2 - return Pow10(m) * Pow10(e-m) -} -func init() { - pow10tab[0] = 1.0e0 - pow10tab[1] = 1.0e1 - for i := 2; i < len(pow10tab); i++ { - m := i / 2 - pow10tab[i] = pow10tab[m] * pow10tab[i-m] + // n < -323 || 308 < n + if n > 0 { + return Inf(1) } + + // n < -323 + return 0 } -- 2.50.0