diff options
Diffstat (limited to 'libgo/go/math')
47 files changed, 1771 insertions, 497 deletions
diff --git a/libgo/go/math/all_test.go b/libgo/go/math/all_test.go index d9ea1fd..3d8cd722 100644 --- a/libgo/go/math/all_test.go +++ b/libgo/go/math/all_test.go @@ -1165,21 +1165,88 @@ var frexpSC = []fi{ {NaN(), 0}, } -var vfgammaSC = []float64{ - Inf(-1), - -3, - Copysign(0, -1), - 0, - Inf(1), - NaN(), -} -var gammaSC = []float64{ - NaN(), - NaN(), - Inf(-1), - Inf(1), - Inf(1), - NaN(), +var vfgamma = [][2]float64{ + {Inf(1), Inf(1)}, + {Inf(-1), NaN()}, + {0, Inf(1)}, + {Copysign(0, -1), Inf(-1)}, + {NaN(), NaN()}, + {-1, NaN()}, + {-2, NaN()}, + {-3, NaN()}, + {-1e16, NaN()}, + {-1e300, NaN()}, + {1.7e308, Inf(1)}, + + // Test inputs inspired by Python test suite. + // Outputs computed at high precision by PARI/GP. + // If recomputing table entries, be careful to use + // high-precision (%.1000g) formatting of the float64 inputs. + // For example, -2.0000000000000004 is the float64 with exact value + // -2.00000000000000044408920985626161695, and + // gamma(-2.0000000000000004) = -1249999999999999.5386078562728167651513, while + // gamma(-2.00000000000000044408920985626161695) = -1125899906826907.2044875028130093136826. + // Thus the table lists -1.1258999068426235e+15 as the answer. + {0.5, 1.772453850905516}, + {1.5, 0.886226925452758}, + {2.5, 1.329340388179137}, + {3.5, 3.3233509704478426}, + {-0.5, -3.544907701811032}, + {-1.5, 2.363271801207355}, + {-2.5, -0.9453087204829419}, + {-3.5, 0.2700882058522691}, + {0.1, 9.51350769866873}, + {0.01, 99.4325851191506}, + {1e-08, 9.999999942278434e+07}, + {1e-16, 1e+16}, + {0.001, 999.4237724845955}, + {1e-16, 1e+16}, + {1e-308, 1e+308}, + {5.6e-309, 1.7857142857142864e+308}, + {5.5e-309, Inf(1)}, + {1e-309, Inf(1)}, + {1e-323, Inf(1)}, + {5e-324, Inf(1)}, + {-0.1, -10.686287021193193}, + {-0.01, -100.58719796441078}, + {-1e-08, -1.0000000057721567e+08}, + {-1e-16, -1e+16}, + {-0.001, -1000.5782056293586}, + {-1e-16, -1e+16}, + {-1e-308, -1e+308}, + {-5.6e-309, -1.7857142857142864e+308}, + {-5.5e-309, Inf(-1)}, + {-1e-309, Inf(-1)}, + {-1e-323, Inf(-1)}, + {-5e-324, Inf(-1)}, + {-0.9999999999999999, -9.007199254740992e+15}, + {-1.0000000000000002, 4.5035996273704955e+15}, + {-1.9999999999999998, 2.2517998136852485e+15}, + {-2.0000000000000004, -1.1258999068426235e+15}, + {-100.00000000000001, -7.540083334883109e-145}, + {-99.99999999999999, 7.540083334884096e-145}, + {17, 2.0922789888e+13}, + {171, 7.257415615307999e+306}, + {171.6, 1.5858969096672565e+308}, + {171.624, 1.7942117599248104e+308}, + {171.625, Inf(1)}, + {172, Inf(1)}, + {2000, Inf(1)}, + {-100.5, -3.3536908198076787e-159}, + {-160.5, -5.255546447007829e-286}, + {-170.5, -3.3127395215386074e-308}, + {-171.5, 1.9316265431712e-310}, + {-176.5, -1.196e-321}, + {-177.5, 5e-324}, + {-178.5, Copysign(0, -1)}, + {-179.5, 0}, + {-201.0001, 0}, + {-202.9999, Copysign(0, -1)}, + {-1000.5, Copysign(0, -1)}, + {-1.0000000003e+09, Copysign(0, -1)}, + {-4.5035996273704955e+15, 0}, + {-63.349078729022985, 4.177797167776188e-88}, + {-127.45117632943295, 1.183111089623681e-214}, } var vfhypotSC = [][2]float64{ @@ -1735,6 +1802,12 @@ var logbBC = []float64{ } func tolerance(a, b, e float64) bool { + // Multiplying by e here can underflow denormal values to zero. + // Check a==b so that at least if a and b are small and identical + // we say they match. + if a == b { + return true + } d := a - b if d < 0 { d = -d @@ -1974,7 +2047,7 @@ func TestExp(t *testing.T) { 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) { + if f := Exp(vf[i]); !veryclose(exp[i], f) { t.Errorf("%s(%g) = %g, want %g", name, vf[i], f, exp[i]) } } @@ -2147,9 +2220,18 @@ func TestGamma(t *testing.T) { t.Errorf("Gamma(%g) = %g, want %g", vf[i], f, gamma[i]) } } - for i := 0; i < len(vfgammaSC); i++ { - if f := Gamma(vfgammaSC[i]); !alike(gammaSC[i], f) { - t.Errorf("Gamma(%g) = %g, want %g", vfgammaSC[i], f, gammaSC[i]) + for _, g := range vfgamma { + f := Gamma(g[0]) + var ok bool + if IsNaN(g[1]) || IsInf(g[1], 0) || g[1] == 0 || f == 0 { + ok = alike(g[1], f) + } else if g[0] > -50 && g[0] <= 171 { + ok = veryclose(g[1], f) + } else { + ok = close(g[1], f) + } + if !ok { + t.Errorf("Gamma(%g) = %g, want %g", g[0], f, g[1]) } } } @@ -3000,27 +3082,36 @@ func BenchmarkSinh(b *testing.B) { var Global float64 -func BenchmarkSqrt(b *testing.B) { +func BenchmarkSqrtIndirect(b *testing.B) { x, y := 0.0, 10.0 + f := Sqrt for i := 0; i < b.N; i++ { - x += Sqrt(y) + x += f(y) } Global = x } -func BenchmarkSqrtIndirect(b *testing.B) { - x, y := 0.0, 10.0 +func BenchmarkSqrtLatency(b *testing.B) { + x := 10.0 + for i := 0; i < b.N; i++ { + x = Sqrt(x) + } + Global = x +} + +func BenchmarkSqrtIndirectLatency(b *testing.B) { + x := 10.0 f := Sqrt for i := 0; i < b.N; i++ { - x += f(y) + x = f(x) } Global = x } -func BenchmarkSqrtGo(b *testing.B) { - x, y := 0.0, 10.0 +func BenchmarkSqrtGoLatency(b *testing.B) { + x := 10.0 for i := 0; i < b.N; i++ { - x += SqrtGo(y) + x = SqrtGo(x) } Global = x } diff --git a/libgo/go/math/arith_s390x.go b/libgo/go/math/arith_s390x.go new file mode 100644 index 0000000..937f25f --- /dev/null +++ b/libgo/go/math/arith_s390x.go @@ -0,0 +1,31 @@ +// Copyright 2016 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. + +// +build ignore + +package math + +func log10TrampolineSetup(x float64) float64 +func log10Asm(x float64) float64 + +func cosTrampolineSetup(x float64) float64 +func cosAsm(x float64) float64 + +func coshTrampolineSetup(x float64) float64 +func coshAsm(x float64) float64 + +func sinTrampolineSetup(x float64) float64 +func sinAsm(x float64) float64 + +func sinhTrampolineSetup(x float64) float64 +func sinhAsm(x float64) float64 + +func tanhTrampolineSetup(x float64) float64 +func tanhAsm(x float64) float64 + +// hasVectorFacility reports whether the machine has the z/Architecture +// vector facility installed and enabled. +func hasVectorFacility() bool + +var hasVX = hasVectorFacility() diff --git a/libgo/go/math/arith_s390x_test.go b/libgo/go/math/arith_s390x_test.go new file mode 100644 index 0000000..fd3e8ca --- /dev/null +++ b/libgo/go/math/arith_s390x_test.go @@ -0,0 +1,146 @@ +// Copyright 2016 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. + +// +build ignore + +// Tests whether the non vector routines are working, even when the tests are run on a +// vector-capable machine. +package math_test + +import ( + . "math" + "testing" +) + +func TestCosNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := CosNoVec(vf[i]); !veryclose(cos[i], f) { + t.Errorf("Cos(%g) = %g, want %g", vf[i], f, cos[i]) + } + } + for i := 0; i < len(vfcosSC); i++ { + if f := CosNoVec(vfcosSC[i]); !alike(cosSC[i], f) { + t.Errorf("Cos(%g) = %g, want %g", vfcosSC[i], f, cosSC[i]) + } + } +} + +func TestCoshNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := CoshNoVec(vf[i]); !close(cosh[i], f) { + t.Errorf("Cosh(%g) = %g, want %g", vf[i], f, cosh[i]) + } + } + for i := 0; i < len(vfcoshSC); i++ { + if f := CoshNoVec(vfcoshSC[i]); !alike(coshSC[i], f) { + t.Errorf("Cosh(%g) = %g, want %g", vfcoshSC[i], f, coshSC[i]) + } + } +} +func TestSinNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := SinNoVec(vf[i]); !veryclose(sin[i], f) { + t.Errorf("Sin(%g) = %g, want %g", vf[i], f, sin[i]) + } + } + for i := 0; i < len(vfsinSC); i++ { + if f := SinNoVec(vfsinSC[i]); !alike(sinSC[i], f) { + t.Errorf("Sin(%g) = %g, want %g", vfsinSC[i], f, sinSC[i]) + } + } +} + +func TestSinhNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := SinhNoVec(vf[i]); !close(sinh[i], f) { + t.Errorf("Sinh(%g) = %g, want %g", vf[i], f, sinh[i]) + } + } + for i := 0; i < len(vfsinhSC); i++ { + if f := SinhNoVec(vfsinhSC[i]); !alike(sinhSC[i], f) { + t.Errorf("Sinh(%g) = %g, want %g", vfsinhSC[i], f, sinhSC[i]) + } + } +} + +// Check that math functions of high angle values +// return accurate results. [Since (vf[i] + large) - large != vf[i], +// testing for Trig(vf[i] + large) == Trig(vf[i]), where large is +// a multiple of 2*Pi, is misleading.] +func TestLargeCosNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + large := float64(100000 * Pi) + for i := 0; i < len(vf); i++ { + f1 := cosLarge[i] + f2 := CosNoVec(vf[i] + large) + if !close(f1, f2) { + t.Errorf("Cos(%g) = %g, want %g", vf[i]+large, f2, f1) + } + } +} + +func TestLargeSinNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + large := float64(100000 * Pi) + for i := 0; i < len(vf); i++ { + f1 := sinLarge[i] + f2 := SinNoVec(vf[i] + large) + if !close(f1, f2) { + t.Errorf("Sin(%g) = %g, want %g", vf[i]+large, f2, f1) + } + } +} + +func TestTanhNovec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + if f := TanhNoVec(vf[i]); !veryclose(tanh[i], f) { + t.Errorf("Tanh(%g) = %g, want %g", vf[i], f, tanh[i]) + } + } + for i := 0; i < len(vftanhSC); i++ { + if f := TanhNoVec(vftanhSC[i]); !alike(tanhSC[i], f) { + t.Errorf("Tanh(%g) = %g, want %g", vftanhSC[i], f, tanhSC[i]) + } + } + +} + +func TestLog10Novec(t *testing.T) { + if !HasVX { + t.Skipf("no vector support") + } + for i := 0; i < len(vf); i++ { + a := Abs(vf[i]) + if f := Log10NoVec(a); !veryclose(log10[i], f) { + t.Errorf("Log10(%g) = %g, want %g", a, f, log10[i]) + } + } + if f := Log10NoVec(E); f != Log10E { + t.Errorf("Log10(%g) = %g, want %g", E, f, Log10E) + } + for i := 0; i < len(vflogSC); i++ { + if f := Log10NoVec(vflogSC[i]); !alike(logSC[i], f) { + t.Errorf("Log10(%g) = %g, want %g", vflogSC[i], f, logSC[i]) + } + } +} diff --git a/libgo/go/math/big/arith_decl_s390x.go b/libgo/go/math/big/arith_decl_s390x.go new file mode 100644 index 0000000..0f11481 --- /dev/null +++ b/libgo/go/math/big/arith_decl_s390x.go @@ -0,0 +1,23 @@ +// Copyright 2016 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. + +// +build !math_big_pure_go + +package big + +func addVV_check(z, x, y []Word) (c Word) +func addVV_vec(z, x, y []Word) (c Word) +func addVV_novec(z, x, y []Word) (c Word) +func subVV_check(z, x, y []Word) (c Word) +func subVV_vec(z, x, y []Word) (c Word) +func subVV_novec(z, x, y []Word) (c Word) +func addVW_check(z, x []Word, y Word) (c Word) +func addVW_vec(z, x []Word, y Word) (c Word) +func addVW_novec(z, x []Word, y Word) (c Word) +func subVW_check(z, x []Word, y Word) (c Word) +func subVW_vec(z, x []Word, y Word) (c Word) +func subVW_novec(z, x []Word, y Word) (c Word) +func hasVectorFacility() bool + +var hasVX = hasVectorFacility() diff --git a/libgo/go/math/big/arith_s390x_test.go b/libgo/go/math/big/arith_s390x_test.go new file mode 100644 index 0000000..ee127a4 --- /dev/null +++ b/libgo/go/math/big/arith_s390x_test.go @@ -0,0 +1,45 @@ +// Copyright 2016 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. + +// +build ignore +// +build s390x !math_big_pure_go + +package big + +import ( + "testing" +) + +// Tests whether the non vector routines are working, even when the tests are run on a +// vector-capable machine + +func TestFunVVnovec(t *testing.T) { + if hasVX == true { + for _, a := range sumVV { + arg := a + testFunVV(t, "addVV_novec", addVV_novec, arg) + + arg = argVV{a.z, a.y, a.x, a.c} + testFunVV(t, "addVV_novec symmetric", addVV_novec, arg) + + arg = argVV{a.x, a.z, a.y, a.c} + testFunVV(t, "subVV_novec", subVV_novec, arg) + + arg = argVV{a.y, a.z, a.x, a.c} + testFunVV(t, "subVV_novec symmetric", subVV_novec, arg) + } + } +} + +func TestFunVWnovec(t *testing.T) { + if hasVX == true { + for _, a := range sumVW { + arg := a + testFunVW(t, "addVW_novec", addVW_novec, arg) + + arg = argVW{a.x, a.z, a.y, a.c} + testFunVW(t, "subVW_novec", subVW_novec, arg) + } + } +} diff --git a/libgo/go/math/big/arith_test.go b/libgo/go/math/big/arith_test.go index 75862b4..f2b3083 100644 --- a/libgo/go/math/big/arith_test.go +++ b/libgo/go/math/big/arith_test.go @@ -6,10 +6,14 @@ package big import ( "fmt" + "internal/testenv" "math/rand" + "strings" "testing" ) +var isRaceBuilder = strings.HasSuffix(testenv.Builder(), "-race") + type funWW func(x, y, c Word) (z1, z0 Word) type argWW struct { x, y, c, z1, z0 Word @@ -123,6 +127,9 @@ var benchSizes = []int{1, 2, 3, 4, 5, 1e1, 1e2, 1e3, 1e4, 1e5} func BenchmarkAddVV(b *testing.B) { for _, n := range benchSizes { + if isRaceBuilder && n > 1e3 { + continue + } x := rndV(n) y := rndV(n) z := make([]Word, n) @@ -233,6 +240,9 @@ func TestFunVW(t *testing.T) { func BenchmarkAddVW(b *testing.B) { for _, n := range benchSizes { + if isRaceBuilder && n > 1e3 { + continue + } x := rndV(n) y := rndW() z := make([]Word, n) @@ -371,6 +381,9 @@ func TestMulAddWWW(t *testing.T) { func BenchmarkAddMulVVW(b *testing.B) { for _, n := range benchSizes { + if isRaceBuilder && n > 1e3 { + continue + } x := rndV(n) y := rndW() z := make([]Word, n) diff --git a/libgo/go/math/big/decimal.go b/libgo/go/math/big/decimal.go index 2c0c9da..2dfa032 100644 --- a/libgo/go/math/big/decimal.go +++ b/libgo/go/math/big/decimal.go @@ -125,11 +125,12 @@ func shr(x *decimal, s uint) { // read a digit, write a digit w := 0 // write index + mask := Word(1)<<s - 1 for r < len(x.mant) { ch := Word(x.mant[r]) r++ d := n >> s - n -= d << s + n &= mask // n -= d << s x.mant[w] = byte(d + '0') w++ n = n*10 + ch - '0' @@ -138,7 +139,7 @@ func shr(x *decimal, s uint) { // write extra digits that still fit for n > 0 && w < len(x.mant) { d := n >> s - n -= d << s + n &= mask x.mant[w] = byte(d + '0') w++ n = n * 10 @@ -148,7 +149,7 @@ func shr(x *decimal, s uint) { // append additional digits that didn't fit for n > 0 { d := n >> s - n -= d << s + n &= mask x.mant = append(x.mant, byte(d+'0')) n = n * 10 } diff --git a/libgo/go/math/big/decimal_test.go b/libgo/go/math/big/decimal_test.go index 15bdb18..424811e 100644 --- a/libgo/go/math/big/decimal_test.go +++ b/libgo/go/math/big/decimal_test.go @@ -4,7 +4,10 @@ package big -import "testing" +import ( + "fmt" + "testing" +) func TestDecimalString(t *testing.T) { for _, test := range []struct { @@ -105,12 +108,27 @@ func TestDecimalRounding(t *testing.T) { } } +var sink string + func BenchmarkDecimalConversion(b *testing.B) { for i := 0; i < b.N; i++ { for shift := -100; shift <= +100; shift++ { var d decimal d.init(natOne, shift) - d.String() + sink = d.String() } } } + +func BenchmarkFloatString(b *testing.B) { + x := new(Float) + for _, prec := range []uint{1e2, 1e3, 1e4, 1e5} { + x.SetPrec(prec).SetRat(NewRat(1, 3)) + b.Run(fmt.Sprintf("%v", prec), func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + sink = x.String() + } + }) + } +} diff --git a/libgo/go/math/big/doc.go b/libgo/go/math/big/doc.go index a3c2375..65ed019 100644 --- a/libgo/go/math/big/doc.go +++ b/libgo/go/math/big/doc.go @@ -31,7 +31,7 @@ setters, for instance: var z1 Int z1.SetUint64(123) // z1 := 123 - z2 := new(Rat).SetFloat64(1.2) // z2 := 6/5 + z2 := new(Rat).SetFloat64(1.25) // z2 := 5/4 z3 := new(Float).SetInt(z1) // z3 := 123.0 Setters, numeric operations and predicates are represented as methods of diff --git a/libgo/go/math/big/float.go b/libgo/go/math/big/float.go index 7a9c2b3..aabd7b4 100644 --- a/libgo/go/math/big/float.go +++ b/libgo/go/math/big/float.go @@ -1210,20 +1210,30 @@ func (z *Float) uadd(x, y *Float) { ex := int64(x.exp) - int64(len(x.mant))*_W ey := int64(y.exp) - int64(len(y.mant))*_W + al := alias(z.mant, x.mant) || alias(z.mant, y.mant) + // TODO(gri) having a combined add-and-shift primitive // could make this code significantly faster switch { case ex < ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(y.mant, uint(ey-ex)) - z.mant = z.mant.add(x.mant, t) + if al { + t := nat(nil).shl(y.mant, uint(ey-ex)) + z.mant = z.mant.add(x.mant, t) + } else { + z.mant = z.mant.shl(y.mant, uint(ey-ex)) + z.mant = z.mant.add(x.mant, z.mant) + } default: // ex == ey, no shift needed z.mant = z.mant.add(x.mant, y.mant) case ex > ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(x.mant, uint(ex-ey)) - z.mant = z.mant.add(t, y.mant) + if al { + t := nat(nil).shl(x.mant, uint(ex-ey)) + z.mant = z.mant.add(t, y.mant) + } else { + z.mant = z.mant.shl(x.mant, uint(ex-ey)) + z.mant = z.mant.add(z.mant, y.mant) + } ex = ey } // len(z.mant) > 0 @@ -1247,18 +1257,28 @@ func (z *Float) usub(x, y *Float) { ex := int64(x.exp) - int64(len(x.mant))*_W ey := int64(y.exp) - int64(len(y.mant))*_W + al := alias(z.mant, x.mant) || alias(z.mant, y.mant) + switch { case ex < ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(y.mant, uint(ey-ex)) - z.mant = t.sub(x.mant, t) + if al { + t := nat(nil).shl(y.mant, uint(ey-ex)) + z.mant = t.sub(x.mant, t) + } else { + z.mant = z.mant.shl(y.mant, uint(ey-ex)) + z.mant = z.mant.sub(x.mant, z.mant) + } default: // ex == ey, no shift needed z.mant = z.mant.sub(x.mant, y.mant) case ex > ey: - // cannot re-use z.mant w/o testing for aliasing - t := nat(nil).shl(x.mant, uint(ex-ey)) - z.mant = t.sub(t, y.mant) + if al { + t := nat(nil).shl(x.mant, uint(ex-ey)) + z.mant = t.sub(t, y.mant) + } else { + z.mant = z.mant.shl(x.mant, uint(ex-ey)) + z.mant = z.mant.sub(z.mant, y.mant) + } ex = ey } diff --git a/libgo/go/math/big/float_test.go b/libgo/go/math/big/float_test.go index 464619b..7d4bd31 100644 --- a/libgo/go/math/big/float_test.go +++ b/libgo/go/math/big/float_test.go @@ -5,6 +5,7 @@ package big import ( + "flag" "fmt" "math" "strconv" @@ -1495,12 +1496,14 @@ func TestFloatQuo(t *testing.T) { } } +var long = flag.Bool("long", false, "run very long tests") + // TestFloatQuoSmoke tests all divisions x/y for values x, y in the range [-n, +n]; // it serves as a smoke test for basic correctness of division. func TestFloatQuoSmoke(t *testing.T) { - n := 1000 - if testing.Short() { - n = 10 + n := 10 + if *long { + n = 1000 } const dprec = 3 // max. precision variation @@ -1762,3 +1765,41 @@ func TestFloatCmpSpecialValues(t *testing.T) { } } } + +func BenchmarkFloatAdd(b *testing.B) { + x := new(Float) + y := new(Float) + z := new(Float) + + for _, prec := range []uint{10, 1e2, 1e3, 1e4, 1e5} { + x.SetPrec(prec).SetRat(NewRat(1, 3)) + y.SetPrec(prec).SetRat(NewRat(1, 6)) + z.SetPrec(prec) + + b.Run(fmt.Sprintf("%v", prec), func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + z.Add(x, y) + } + }) + } +} + +func BenchmarkFloatSub(b *testing.B) { + x := new(Float) + y := new(Float) + z := new(Float) + + for _, prec := range []uint{10, 1e2, 1e3, 1e4, 1e5} { + x.SetPrec(prec).SetRat(NewRat(1, 3)) + y.SetPrec(prec).SetRat(NewRat(1, 6)) + z.SetPrec(prec) + + b.Run(fmt.Sprintf("%v", prec), func(b *testing.B) { + b.ReportAllocs() + for i := 0; i < b.N; i++ { + z.Sub(x, y) + } + }) + } +} diff --git a/libgo/go/math/big/floatconv.go b/libgo/go/math/big/floatconv.go index a884df6..95d1bf8 100644 --- a/libgo/go/math/big/floatconv.go +++ b/libgo/go/math/big/floatconv.go @@ -12,9 +12,13 @@ import ( "strings" ) +var floatZero Float + // SetString sets z to the value of s and returns z and a boolean indicating // success. s must be a floating-point number of the same format as accepted -// by Parse, with base argument 0. +// by Parse, with base argument 0. The entire string (not just a prefix) must +// be valid for success. If the operation failed, the value of z is undefined +// but the returned value is nil. func (z *Float) SetString(s string) (*Float, bool) { if f, _, err := z.Parse(s, 0); err == nil { return f, true @@ -212,17 +216,18 @@ func (z *Float) pow5(n uint64) *Float { // // It sets z to the (possibly rounded) value of the corresponding floating- // point value, and returns z, the actual base b, and an error err, if any. +// The entire string (not just a prefix) must be consumed for success. // If z's precision is 0, it is changed to 64 before rounding takes effect. // The number must be of the form: // // number = [ sign ] [ prefix ] mantissa [ exponent ] | infinity . // sign = "+" | "-" . -// prefix = "0" ( "x" | "X" | "b" | "B" ) . +// prefix = "0" ( "x" | "X" | "b" | "B" ) . // mantissa = digits | digits "." [ digits ] | "." digits . // exponent = ( "E" | "e" | "p" ) [ sign ] digits . // digits = digit { digit } . // digit = "0" ... "9" | "a" ... "z" | "A" ... "Z" . -// infinity = [ sign ] ( "inf" | "Inf" ) . +// infinity = [ sign ] ( "inf" | "Inf" ) . // // The base argument must be 0, 2, 10, or 16. Providing an invalid base // argument will lead to a run-time panic. @@ -273,3 +278,16 @@ func (z *Float) Parse(s string, base int) (f *Float, b int, err error) { func ParseFloat(s string, base int, prec uint, mode RoundingMode) (f *Float, b int, err error) { return new(Float).SetPrec(prec).SetMode(mode).Parse(s, base) } + +var _ fmt.Scanner = &floatZero // *Float must implement fmt.Scanner + +// Scan is a support routine for fmt.Scanner; it sets z to the value of +// the scanned number. It accepts formats whose verbs are supported by +// fmt.Scan for floating point values, which are: +// 'b' (binary), 'e', 'E', 'f', 'F', 'g' and 'G'. +// Scan doesn't handle ±Inf. +func (z *Float) Scan(s fmt.ScanState, ch rune) error { + s.SkipSpace() + _, _, err := z.scan(byteReader{s}, 0) + return err +} diff --git a/libgo/go/math/big/floatconv_test.go b/libgo/go/math/big/floatconv_test.go index b2a1ab0..edcb2eb 100644 --- a/libgo/go/math/big/floatconv_test.go +++ b/libgo/go/math/big/floatconv_test.go @@ -5,6 +5,7 @@ package big import ( + "bytes" "fmt" "math" "strconv" @@ -665,3 +666,54 @@ func BenchmarkParseFloatLargeExp(b *testing.B) { } } } + +func TestFloatScan(t *testing.T) { + var floatScanTests = []struct { + input string + format string + output string + remaining int + wantErr bool + }{ + 0: {"10.0", "%f", "10", 0, false}, + 1: {"23.98+2.0", "%v", "23.98", 4, false}, + 2: {"-1+1", "%v", "-1", 2, false}, + 3: {" 00000", "%v", "0", 0, false}, + 4: {"-123456p-78", "%b", "-4.084816388e-19", 0, false}, + 5: {"+123", "%b", "123", 0, false}, + 6: {"-1.234e+56", "%e", "-1.234e+56", 0, false}, + 7: {"-1.234E-56", "%E", "-1.234e-56", 0, false}, + 8: {"-1.234e+567", "%g", "-1.234e+567", 0, false}, + 9: {"+1234567891011.234", "%G", "1.234567891e+12", 0, false}, + + // Scan doesn't handle ±Inf. + 10: {"Inf", "%v", "", 3, true}, + 11: {"-Inf", "%v", "", 3, true}, + 12: {"-Inf", "%v", "", 3, true}, + } + + var buf bytes.Buffer + for i, test := range floatScanTests { + x := new(Float) + buf.Reset() + buf.WriteString(test.input) + _, err := fmt.Fscanf(&buf, test.format, x) + if test.wantErr { + if err == nil { + t.Errorf("#%d want non-nil err", i) + } + continue + } + + if err != nil { + t.Errorf("#%d error: %s", i, err) + } + + if x.String() != test.output { + t.Errorf("#%d got %s; want %s", i, x.String(), test.output) + } + if buf.Len() != test.remaining { + t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining) + } + } +} diff --git a/libgo/go/math/big/floatexample_test.go b/libgo/go/math/big/floatexample_test.go index 05bce61..8645c44 100644 --- a/libgo/go/math/big/floatexample_test.go +++ b/libgo/go/math/big/floatexample_test.go @@ -13,7 +13,7 @@ import ( ) func ExampleFloat_Add() { - // Operating on numbers of different precision. + // Operate on numbers of different precision. var x, y, z big.Float x.SetInt64(1000) // x is automatically set to 64bit precision y.SetFloat64(2.718281828) // y is automatically set to 53bit precision @@ -28,8 +28,8 @@ func ExampleFloat_Add() { // z = 1002.718282 (0x.faadf854p+10, prec = 32, acc = Below) } -func Example_Shift() { - // Implementing Float "shift" by modifying the (binary) exponents directly. +func ExampleFloat_shift() { + // Implement Float "shift" by modifying the (binary) exponents directly. for s := -5; s <= 5; s++ { x := big.NewFloat(0.5) x.SetMantExp(x, x.MantExp(nil)+s) // shift x by s diff --git a/libgo/go/math/big/floatmarsh.go b/libgo/go/math/big/floatmarsh.go index 3725d4b..d1c1dab 100644 --- a/libgo/go/math/big/floatmarsh.go +++ b/libgo/go/math/big/floatmarsh.go @@ -16,7 +16,7 @@ const floatGobVersion byte = 1 // GobEncode implements the gob.GobEncoder interface. // The Float value and all its attributes (precision, -// rounding mode, accuracy) are marshalled. +// rounding mode, accuracy) are marshaled. func (x *Float) GobEncode() ([]byte, error) { if x == nil { return nil, nil diff --git a/libgo/go/math/big/ftoa.go b/libgo/go/math/big/ftoa.go index 57b16e1..d2a8588 100644 --- a/libgo/go/math/big/ftoa.go +++ b/libgo/go/math/big/ftoa.go @@ -376,6 +376,8 @@ func min(x, y int) int { return y } +var _ fmt.Formatter = &floatZero // *Float must implement fmt.Formatter + // Format implements fmt.Formatter. It accepts all the regular // formats for floating-point numbers ('b', 'e', 'E', 'f', 'F', // 'g', 'G') as well as 'p' and 'v'. See (*Float).Text for the diff --git a/libgo/go/math/big/gcd_test.go b/libgo/go/math/big/gcd_test.go index a929bf5..3cca2ec 100644 --- a/libgo/go/math/big/gcd_test.go +++ b/libgo/go/math/big/gcd_test.go @@ -20,6 +20,9 @@ func randInt(r *rand.Rand, size uint) *Int { } func runGCD(b *testing.B, aSize, bSize uint) { + if isRaceBuilder && (aSize > 1000 || bSize > 1000) { + b.Skip("skipping on race builder") + } b.Run("WithoutXY", func(b *testing.B) { runGCDExt(b, aSize, bSize, false) }) diff --git a/libgo/go/math/big/int.go b/libgo/go/math/big/int.go index f2a75d1..1d8dabc 100644 --- a/libgo/go/math/big/int.go +++ b/libgo/go/math/big/int.go @@ -361,7 +361,8 @@ func (x *Int) Uint64() uint64 { } // SetString sets z to the value of s, interpreted in the given base, -// and returns z and a boolean indicating success. If SetString fails, +// and returns z and a boolean indicating success. The entire string +// (not just a prefix) must be valid for success. If SetString fails, // the value of z is undefined but the returned value is nil. // // The base argument must be 0 or a value between 2 and MaxBase. If the base @@ -371,12 +372,11 @@ func (x *Int) Uint64() uint64 { // func (z *Int) SetString(s string, base int) (*Int, bool) { r := strings.NewReader(s) - _, _, err := z.scan(r, base) - if err != nil { + if _, _, err := z.scan(r, base); err != nil { return nil, false } - _, err = r.ReadByte() - if err != io.EOF { + // entire string must have been consumed + if _, err := r.ReadByte(); err != io.EOF { return nil, false } return z, true // err == io.EOF => scan consumed all of s @@ -404,8 +404,11 @@ func (x *Int) BitLen() int { // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. // If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. -// See Knuth, volume 2, section 4.6.3. +// +// Modular exponentation of inputs of a particular size is not a +// cryptographically constant-time operation. func (z *Int) Exp(x, y, m *Int) *Int { + // See Knuth, volume 2, section 4.6.3. var yWords nat if !y.neg { yWords = y.abs @@ -550,19 +553,6 @@ func (z *Int) binaryGCD(a, b *Int) *Int { return z.Lsh(u, k) } -// ProbablyPrime performs n Miller-Rabin tests to check whether x is prime. -// If x is prime, it returns true. -// If x is not prime, it returns false with probability at least 1 - ¼ⁿ. -// -// It is not suitable for judging primes that an adversary may have crafted -// to fool this test. -func (x *Int) ProbablyPrime(n int) bool { - if n <= 0 { - panic("non-positive n for ProbablyPrime") - } - return !x.neg && x.abs.probablyPrime(n) -} - // Rand sets z to a pseudo-random number in [0, n) and returns z. func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int { z.neg = false @@ -577,6 +567,11 @@ func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int { // ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ // and returns z. If g and n are not relatively prime, the result is undefined. func (z *Int) ModInverse(g, n *Int) *Int { + if g.neg { + // GCD expects parameters a and b to be > 0. + var g2 Int + g = g2.Mod(g, n) + } var d Int d.GCD(z, nil, g, n) // x and y are such that g*x + n*y = d. Since g and n are @@ -932,3 +927,14 @@ func (z *Int) Not(x *Int) *Int { z.neg = true // z cannot be zero if x is positive return z } + +// Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z. +// It panics if x is negative. +func (z *Int) Sqrt(x *Int) *Int { + if x.neg { + panic("square root of negative number") + } + z.neg = false + z.abs = z.abs.sqrt(x.abs) + return z +} diff --git a/libgo/go/math/big/int_test.go b/libgo/go/math/big/int_test.go index 45a3765..b8e0778 100644 --- a/libgo/go/math/big/int_test.go +++ b/libgo/go/math/big/int_test.go @@ -9,6 +9,7 @@ import ( "encoding/hex" "fmt" "math/rand" + "strings" "testing" "testing/quick" ) @@ -478,6 +479,18 @@ func TestQuoStepD6(t *testing.T) { } } +func BenchmarkQuoRem(b *testing.B) { + x, _ := new(Int).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0) + y, _ := new(Int).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0) + q := new(Int) + r := new(Int) + + b.ResetTimer() + for i := 0; i < b.N; i++ { + q.QuoRem(y, x, r) + } +} + var bitLenTests = []struct { in string out int @@ -572,6 +585,19 @@ var expTests = []struct { {"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"}, {"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"}, {"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"}, + + { + "2", + "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD", + "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", // odd + "0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF", + }, + { + "2", + "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD", + "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", // even + "0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A", + }, } func TestExp(t *testing.T) { @@ -614,6 +640,26 @@ func TestExp(t *testing.T) { } } +func BenchmarkExp(b *testing.B) { + x, _ := new(Int).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0) + y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0) + n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0) + out := new(Int) + for i := 0; i < b.N; i++ { + out.Exp(x, y, n) + } +} + +func BenchmarkExp2(b *testing.B) { + x, _ := new(Int).SetString("2", 0) + y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0) + n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0) + out := new(Int) + for i := 0; i < b.N; i++ { + out.Exp(x, y, n) + } +} + func checkGcd(aBytes, bBytes []byte) bool { x := new(Int) y := new(Int) @@ -715,85 +761,6 @@ func TestGcd(t *testing.T) { } } -var primes = []string{ - "2", - "3", - "5", - "7", - "11", - - "13756265695458089029", - "13496181268022124907", - "10953742525620032441", - "17908251027575790097", - - // https://golang.org/issue/638 - "18699199384836356663", - - "98920366548084643601728869055592650835572950932266967461790948584315647051443", - "94560208308847015747498523884063394671606671904944666360068158221458669711639", - - // http://primes.utm.edu/lists/small/small3.html - "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163", - "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593", - "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993", - "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", - - // ECC primes: http://tools.ietf.org/html/draft-ladd-safecurves-02 - "3618502788666131106986593281521497120414687020801267626233049500247285301239", // Curve1174: 2^251-9 - "57896044618658097711785492504343953926634992332820282019728792003956564819949", // Curve25519: 2^255-19 - "9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599", // E-382: 2^382-105 - "42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367", // Curve41417: 2^414-17 - "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", // E-521: 2^521-1 -} - -var composites = []string{ - "0", - "1", - "21284175091214687912771199898307297748211672914763848041968395774954376176754", - "6084766654921918907427900243509372380954290099172559290432744450051395395951", - "84594350493221918389213352992032324280367711247940675652888030554255915464401", - "82793403787388584738507275144194252681", -} - -func TestProbablyPrime(t *testing.T) { - nreps := 20 - if testing.Short() { - nreps = 1 - } - for i, s := range primes { - p, _ := new(Int).SetString(s, 10) - if !p.ProbablyPrime(nreps) { - t.Errorf("#%d prime found to be non-prime (%s)", i, s) - } - } - - for i, s := range composites { - c, _ := new(Int).SetString(s, 10) - if c.ProbablyPrime(nreps) { - t.Errorf("#%d composite found to be prime (%s)", i, s) - } - if testing.Short() { - break - } - } - - // check that ProbablyPrime panics if n <= 0 - c := NewInt(11) // a prime - for _, n := range []int{-1, 0, 1} { - func() { - defer func() { - if n <= 0 && recover() == nil { - t.Fatalf("expected panic from ProbablyPrime(%d)", n) - } - }() - if !c.ProbablyPrime(n) { - t.Fatalf("%v should be a prime", c) - } - }() - } -} - type intShiftTest struct { in string shift uint @@ -1229,6 +1196,9 @@ func BenchmarkModSqrt224_3Mod4(b *testing.B) { } func BenchmarkModSqrt5430_Tonelli(b *testing.B) { + if isRaceBuilder { + b.Skip("skipping on race builder") + } p := tri(5430) x := new(Int).SetUint64(2) for i := 0; i < b.N; i++ { @@ -1238,6 +1208,9 @@ func BenchmarkModSqrt5430_Tonelli(b *testing.B) { } func BenchmarkModSqrt5430_3Mod4(b *testing.B) { + if isRaceBuilder { + b.Skip("skipping on race builder") + } p := tri(5430) x := new(Int).SetUint64(2) for i := 0; i < b.N; i++ { @@ -1303,6 +1276,7 @@ var modInverseTests = []struct { }{ {"1234567", "458948883992"}, {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"}, + {"-10", "13"}, // issue #16984 } func TestModInverse(t *testing.T) { @@ -1480,3 +1454,44 @@ func TestIssue2607(t *testing.T) { n := NewInt(10) n.Rand(rand.New(rand.NewSource(9)), n) } + +func TestSqrt(t *testing.T) { + root := 0 + r := new(Int) + for i := 0; i < 10000; i++ { + if (root+1)*(root+1) <= i { + root++ + } + n := NewInt(int64(i)) + r.SetInt64(-2) + r.Sqrt(n) + if r.Cmp(NewInt(int64(root))) != 0 { + t.Errorf("Sqrt(%v) = %v, want %v", n, r, root) + } + } + + for i := 0; i < 1000; i += 10 { + n, _ := new(Int).SetString("1"+strings.Repeat("0", i), 10) + r := new(Int).Sqrt(n) + root, _ := new(Int).SetString("1"+strings.Repeat("0", i/2), 10) + if r.Cmp(root) != 0 { + t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2) + } + } + + // Test aliasing. + r.SetInt64(100) + r.Sqrt(r) + if r.Int64() != 10 { + t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64()) + } +} + +func BenchmarkSqrt(b *testing.B) { + n, _ := new(Int).SetString("1"+strings.Repeat("0", 1001), 10) + b.ResetTimer() + t := new(Int) + for i := 0; i < b.N; i++ { + t.Sqrt(n) + } +} diff --git a/libgo/go/math/big/intconv.go b/libgo/go/math/big/intconv.go index daf674ae..91a62ce 100644 --- a/libgo/go/math/big/intconv.go +++ b/libgo/go/math/big/intconv.go @@ -52,6 +52,8 @@ func writeMultiple(s fmt.State, text string, count int) { } } +var _ fmt.Formatter = intOne // *Int must implement fmt.Formatter + // Format implements fmt.Formatter. It accepts the formats // 'b' (binary), 'o' (octal), 'd' (decimal), 'x' (lowercase // hexadecimal), and 'X' (uppercase hexadecimal). @@ -223,6 +225,8 @@ func (r byteReader) UnreadByte() error { return r.UnreadRune() } +var _ fmt.Scanner = intOne // *Int must implement fmt.Scanner + // Scan is a support routine for fmt.Scanner; it sets z to the value of // the scanned number. It accepts the formats 'b' (binary), 'o' (octal), // 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal). diff --git a/libgo/go/math/big/intmarsh.go b/libgo/go/math/big/intmarsh.go index 4ff57b6..ee1e414 100644 --- a/libgo/go/math/big/intmarsh.go +++ b/libgo/go/math/big/intmarsh.go @@ -59,7 +59,7 @@ func (z *Int) UnmarshalText(text []byte) error { return nil } -// The JSON marshallers are only here for API backward compatibility +// The JSON marshalers are only here for API backward compatibility // (programs that explicitly look for these two methods). JSON works // fine with the TextMarshaler only. @@ -70,5 +70,9 @@ func (x *Int) MarshalJSON() ([]byte, error) { // UnmarshalJSON implements the json.Unmarshaler interface. func (z *Int) UnmarshalJSON(text []byte) error { + // Ignore null, like in the main JSON package. + if string(text) == "null" { + return nil + } return z.UnmarshalText(text) } diff --git a/libgo/go/math/big/nat.go b/libgo/go/math/big/nat.go index 2e65d2a..9b1a626 100644 --- a/libgo/go/math/big/nat.go +++ b/libgo/go/math/big/nat.go @@ -542,16 +542,21 @@ func (z nat) div(z2, u, v nat) (q, r nat) { return } -// getNat returns a nat of len n. The contents may not be zero. -func getNat(n int) nat { - var z nat +// getNat returns a *nat of len n. The contents may not be zero. +// The pool holds *nat to avoid allocation when converting to interface{}. +func getNat(n int) *nat { + var z *nat if v := natPool.Get(); v != nil { - z = v.(nat) + z = v.(*nat) } - return z.make(n) + if z == nil { + z = new(nat) + } + *z = z.make(n) + return z } -func putNat(x nat) { +func putNat(x *nat) { natPool.Put(x) } @@ -575,7 +580,8 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) { } q = z.make(m + 1) - qhatv := getNat(n + 1) + qhatvp := getNat(n + 1) + qhatv := *qhatvp if alias(u, uIn) || alias(u, v) { u = nil // u is an alias for uIn or v - cannot reuse } @@ -583,36 +589,40 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) { u.clear() // TODO(gri) no need to clear if we allocated a new u // D1. - var v1 nat + var v1p *nat shift := nlz(v[n-1]) if shift > 0 { // do not modify v, it may be used by another goroutine simultaneously - v1 = getNat(n) + v1p = getNat(n) + v1 := *v1p shlVU(v1, v, shift) v = v1 } u[len(uIn)] = shlVU(u[0:len(uIn)], uIn, shift) // D2. + vn1 := v[n-1] for j := m; j >= 0; j-- { // D3. qhat := Word(_M) - if u[j+n] != v[n-1] { + if ujn := u[j+n]; ujn != vn1 { var rhat Word - qhat, rhat = divWW(u[j+n], u[j+n-1], v[n-1]) + qhat, rhat = divWW(ujn, u[j+n-1], vn1) // x1 | x2 = q̂v_{n-2} - x1, x2 := mulWW(qhat, v[n-2]) + vn2 := v[n-2] + x1, x2 := mulWW(qhat, vn2) // test if q̂v_{n-2} > br̂ + u_{j+n-2} - for greaterThan(x1, x2, rhat, u[j+n-2]) { + ujn2 := u[j+n-2] + for greaterThan(x1, x2, rhat, ujn2) { qhat-- prevRhat := rhat - rhat += v[n-1] + rhat += vn1 // v[n-1] >= 0, so this tests for overflow. if rhat < prevRhat { break } - x1, x2 = mulWW(qhat, v[n-2]) + x1, x2 = mulWW(qhat, vn2) } } @@ -628,10 +638,10 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) { q[j] = qhat } - if v1 != nil { - putNat(v1) + if v1p != nil { + putNat(v1p) } - putNat(qhatv) + putNat(qhatvp) q = q.norm() shrVU(u, u, shift) @@ -650,14 +660,14 @@ func (x nat) bitLen() int { const deBruijn32 = 0x077CB531 -var deBruijn32Lookup = []byte{ +var deBruijn32Lookup = [...]byte{ 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9, } const deBruijn64 = 0x03f79d71b4ca8b09 -var deBruijn64Lookup = []byte{ +var deBruijn64Lookup = [...]byte{ 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, @@ -950,7 +960,7 @@ func (z nat) expNN(x, y, m nat) nat { // (x^2...x^15) but then reduces the number of multiply-reduces by a // third. Even for a 32-bit exponent, this reduces the number of // operations. Uses Montgomery method for odd moduli. - if len(x) > 1 && len(y) > 1 && len(m) > 0 { + if x.cmp(natOne) > 0 && len(y) > 1 && len(m) > 0 { if m[0]&1 == 1 { return z.expNNMontgomery(x, y, m) } @@ -1169,96 +1179,6 @@ func (z nat) expNNMontgomery(x, y, m nat) nat { return zz.norm() } -// probablyPrime performs n Miller-Rabin tests to check whether x is prime. -// If x is prime, it returns true. -// If x is not prime, it returns false with probability at least 1 - ¼ⁿ. -// -// It is not suitable for judging primes that an adversary may have crafted -// to fool this test. -func (n nat) probablyPrime(reps int) bool { - if len(n) == 0 { - return false - } - - if len(n) == 1 { - if n[0] < 2 { - return false - } - - if n[0]%2 == 0 { - return n[0] == 2 - } - - // We have to exclude these cases because we reject all - // multiples of these numbers below. - switch n[0] { - case 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53: - return true - } - } - - if n[0]&1 == 0 { - return false // n is even - } - - const primesProduct32 = 0xC0CFD797 // Π {p ∈ primes, 2 < p <= 29} - const primesProduct64 = 0xE221F97C30E94E1D // Π {p ∈ primes, 2 < p <= 53} - - var r Word - switch _W { - case 32: - r = n.modW(primesProduct32) - case 64: - r = n.modW(primesProduct64 & _M) - default: - panic("Unknown word size") - } - - if r%3 == 0 || r%5 == 0 || r%7 == 0 || r%11 == 0 || - r%13 == 0 || r%17 == 0 || r%19 == 0 || r%23 == 0 || r%29 == 0 { - return false - } - - if _W == 64 && (r%31 == 0 || r%37 == 0 || r%41 == 0 || - r%43 == 0 || r%47 == 0 || r%53 == 0) { - return false - } - - nm1 := nat(nil).sub(n, natOne) - // determine q, k such that nm1 = q << k - k := nm1.trailingZeroBits() - q := nat(nil).shr(nm1, k) - - nm3 := nat(nil).sub(nm1, natTwo) - rand := rand.New(rand.NewSource(int64(n[0]))) - - var x, y, quotient nat - nm3Len := nm3.bitLen() - -NextRandom: - for i := 0; i < reps; i++ { - x = x.random(rand, nm3, nm3Len) - x = x.add(x, natTwo) - y = y.expNN(x, q, n) - if y.cmp(natOne) == 0 || y.cmp(nm1) == 0 { - continue - } - for j := uint(1); j < k; j++ { - y = y.mul(y, y) - quotient, y = quotient.div(y, y, n) - if y.cmp(nm1) == 0 { - continue NextRandom - } - if y.cmp(natOne) == 0 { - return false - } - } - return false - } - - return true -} - // bytes writes the value of z into buf using big-endian encoding. // len(buf) must be >= len(z)*_S. The value of z is encoded in the // slice buf[i:]. The number i of unused bytes at the beginning of @@ -1303,3 +1223,37 @@ func (z nat) setBytes(buf []byte) nat { return z.norm() } + +// sqrt sets z = ⌊√x⌋ +func (z nat) sqrt(x nat) nat { + if x.cmp(natOne) <= 0 { + return z.set(x) + } + if alias(z, x) { + z = nil + } + + // Start with value known to be too large and repeat "z = ⌊(z + ⌊x/z⌋)/2⌋" until it stops getting smaller. + // See Brent and Zimmermann, Modern Computer Arithmetic, Algorithm 1.13 (SqrtInt). + // https://members.loria.fr/PZimmermann/mca/pub226.html + // If x is one less than a perfect square, the sequence oscillates between the correct z and z+1; + // otherwise it converges to the correct z and stays there. + var z1, z2 nat + z1 = z + z1 = z1.setUint64(1) + z1 = z1.shl(z1, uint(x.bitLen()/2+1)) // must be ≥ √x + for n := 0; ; n++ { + z2, _ = z2.div(nil, x, z1) + z2 = z2.add(z2, z1) + z2 = z2.shr(z2, 1) + if z2.cmp(z1) >= 0 { + // z1 is answer. + // Figure out whether z1 or z2 is currently aliased to z by looking at loop count. + if n&1 == 0 { + return z1 + } + return z.set(z1) + } + z1, z2 = z2, z1 + } +} diff --git a/libgo/go/math/big/natconv_test.go b/libgo/go/math/big/natconv_test.go index 79901d1..bdb60e6 100644 --- a/libgo/go/math/big/natconv_test.go +++ b/libgo/go/math/big/natconv_test.go @@ -278,6 +278,9 @@ func BenchmarkScan(b *testing.B) { const x = 10 for _, base := range []int{2, 8, 10, 16} { for _, y := range []Word{10, 100, 1000, 10000, 100000} { + if isRaceBuilder && y > 1000 { + continue + } b.Run(fmt.Sprintf("%d/Base%d", y, base), func(b *testing.B) { b.StopTimer() var z nat @@ -301,6 +304,9 @@ func BenchmarkString(b *testing.B) { const x = 10 for _, base := range []int{2, 8, 10, 16} { for _, y := range []Word{10, 100, 1000, 10000, 100000} { + if isRaceBuilder && y > 1000 { + continue + } b.Run(fmt.Sprintf("%d/Base%d", y, base), func(b *testing.B) { b.StopTimer() var z nat diff --git a/libgo/go/math/big/prime.go b/libgo/go/math/big/prime.go new file mode 100644 index 0000000..3e9690e --- /dev/null +++ b/libgo/go/math/big/prime.go @@ -0,0 +1,320 @@ +// Copyright 2016 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 big + +import "math/rand" + +// ProbablyPrime reports whether x is probably prime, +// applying the Miller-Rabin test with n pseudorandomly chosen bases +// as well as a Baillie-PSW test. +// +// If x is prime, ProbablyPrime returns true. +// If x is chosen randomly and not prime, ProbablyPrime probably returns false. +// The probability of returning true for a randomly chosen non-prime is at most ¼ⁿ. +// +// ProbablyPrime is 100% accurate for inputs less than 2⁶⁴. +// See Menezes et al., Handbook of Applied Cryptography, 1997, pp. 145-149, +// and FIPS 186-4 Appendix F for further discussion of the error probabilities. +// +// ProbablyPrime is not suitable for judging primes that an adversary may +// have crafted to fool the test. +// +// As of Go 1.8, ProbablyPrime(0) is allowed and applies only a Baillie-PSW test. +// Before Go 1.8, ProbablyPrime applied only the Miller-Rabin tests, and ProbablyPrime(0) panicked. +func (x *Int) ProbablyPrime(n int) bool { + // Note regarding the doc comment above: + // It would be more precise to say that the Baillie-PSW test uses the + // extra strong Lucas test as its Lucas test, but since no one knows + // how to tell any of the Lucas tests apart inside a Baillie-PSW test + // (they all work equally well empirically), that detail need not be + // documented or implicitly guaranteed. + // The comment does avoid saying "the" Baillie-PSW test + // because of this general ambiguity. + + if n < 0 { + panic("negative n for ProbablyPrime") + } + if x.neg || len(x.abs) == 0 { + return false + } + + // primeBitMask records the primes < 64. + const primeBitMask uint64 = 1<<2 | 1<<3 | 1<<5 | 1<<7 | + 1<<11 | 1<<13 | 1<<17 | 1<<19 | 1<<23 | 1<<29 | 1<<31 | + 1<<37 | 1<<41 | 1<<43 | 1<<47 | 1<<53 | 1<<59 | 1<<61 + + w := x.abs[0] + if len(x.abs) == 1 && w < 64 { + return primeBitMask&(1<<w) != 0 + } + + if w&1 == 0 { + return false // n is even + } + + const primesA = 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 37 + const primesB = 29 * 31 * 41 * 43 * 47 * 53 + + var rA, rB uint32 + switch _W { + case 32: + rA = uint32(x.abs.modW(primesA)) + rB = uint32(x.abs.modW(primesB)) + case 64: + r := x.abs.modW((primesA * primesB) & _M) + rA = uint32(r % primesA) + rB = uint32(r % primesB) + default: + panic("math/big: invalid word size") + } + + if rA%3 == 0 || rA%5 == 0 || rA%7 == 0 || rA%11 == 0 || rA%13 == 0 || rA%17 == 0 || rA%19 == 0 || rA%23 == 0 || rA%37 == 0 || + rB%29 == 0 || rB%31 == 0 || rB%41 == 0 || rB%43 == 0 || rB%47 == 0 || rB%53 == 0 { + return false + } + + return x.abs.probablyPrimeMillerRabin(n+1, true) && x.abs.probablyPrimeLucas() +} + +// probablyPrimeMillerRabin reports whether n passes reps rounds of the +// Miller-Rabin primality test, using pseudo-randomly chosen bases. +// If force2 is true, one of the rounds is forced to use base 2. +// See Handbook of Applied Cryptography, p. 139, Algorithm 4.24. +// The number n is known to be non-zero. +func (n nat) probablyPrimeMillerRabin(reps int, force2 bool) bool { + nm1 := nat(nil).sub(n, natOne) + // determine q, k such that nm1 = q << k + k := nm1.trailingZeroBits() + q := nat(nil).shr(nm1, k) + + nm3 := nat(nil).sub(nm1, natTwo) + rand := rand.New(rand.NewSource(int64(n[0]))) + + var x, y, quotient nat + nm3Len := nm3.bitLen() + +NextRandom: + for i := 0; i < reps; i++ { + if i == reps-1 && force2 { + x = x.set(natTwo) + } else { + x = x.random(rand, nm3, nm3Len) + x = x.add(x, natTwo) + } + y = y.expNN(x, q, n) + if y.cmp(natOne) == 0 || y.cmp(nm1) == 0 { + continue + } + for j := uint(1); j < k; j++ { + y = y.mul(y, y) + quotient, y = quotient.div(y, y, n) + if y.cmp(nm1) == 0 { + continue NextRandom + } + if y.cmp(natOne) == 0 { + return false + } + } + return false + } + + return true +} + +// probablyPrimeLucas reports whether n passes the "almost extra strong" Lucas probable prime test, +// using Baillie-OEIS parameter selection. This corresponds to "AESLPSP" on Jacobsen's tables (link below). +// The combination of this test and a Miller-Rabin/Fermat test with base 2 gives a Baillie-PSW test. +// +// References: +// +// Baillie and Wagstaff, "Lucas Pseudoprimes", Mathematics of Computation 35(152), +// October 1980, pp. 1391-1417, especially page 1401. +// http://www.ams.org/journals/mcom/1980-35-152/S0025-5718-1980-0583518-6/S0025-5718-1980-0583518-6.pdf +// +// Grantham, "Frobenius Pseudoprimes", Mathematics of Computation 70(234), +// March 2000, pp. 873-891. +// http://www.ams.org/journals/mcom/2001-70-234/S0025-5718-00-01197-2/S0025-5718-00-01197-2.pdf +// +// Baillie, "Extra strong Lucas pseudoprimes", OEIS A217719, https://oeis.org/A217719. +// +// Jacobsen, "Pseudoprime Statistics, Tables, and Data", http://ntheory.org/pseudoprimes.html. +// +// Nicely, "The Baillie-PSW Primality Test", http://www.trnicely.net/misc/bpsw.html. +// (Note that Nicely's definition of the "extra strong" test gives the wrong Jacobi condition, +// as pointed out by Jacobsen.) +// +// Crandall and Pomerance, Prime Numbers: A Computational Perspective, 2nd ed. +// Springer, 2005. +func (n nat) probablyPrimeLucas() bool { + // Discard 0, 1. + if len(n) == 0 || n.cmp(natOne) == 0 { + return false + } + // Two is the only even prime. + // Already checked by caller, but here to allow testing in isolation. + if n[0]&1 == 0 { + return n.cmp(natTwo) == 0 + } + + // Baillie-OEIS "method C" for choosing D, P, Q, + // as in https://oeis.org/A217719/a217719.txt: + // try increasing P ≥ 3 such that D = P² - 4 (so Q = 1) + // until Jacobi(D, n) = -1. + // The search is expected to succeed for non-square n after just a few trials. + // After more than expected failures, check whether n is square + // (which would cause Jacobi(D, n) = 1 for all D not dividing n). + p := Word(3) + d := nat{1} + t1 := nat(nil) // temp + intD := &Int{abs: d} + intN := &Int{abs: n} + for ; ; p++ { + if p > 10000 { + // This is widely believed to be impossible. + // If we get a report, we'll want the exact number n. + panic("math/big: internal error: cannot find (D/n) = -1 for " + intN.String()) + } + d[0] = p*p - 4 + j := Jacobi(intD, intN) + if j == -1 { + break + } + if j == 0 { + // d = p²-4 = (p-2)(p+2). + // If (d/n) == 0 then d shares a prime factor with n. + // Since the loop proceeds in increasing p and starts with p-2==1, + // the shared prime factor must be p+2. + // If p+2 == n, then n is prime; otherwise p+2 is a proper factor of n. + return len(n) == 1 && n[0] == p+2 + } + if p == 40 { + // We'll never find (d/n) = -1 if n is a square. + // If n is a non-square we expect to find a d in just a few attempts on average. + // After 40 attempts, take a moment to check if n is indeed a square. + t1 = t1.sqrt(n) + t1 = t1.mul(t1, t1) + if t1.cmp(n) == 0 { + return false + } + } + } + + // Grantham definition of "extra strong Lucas pseudoprime", after Thm 2.3 on p. 876 + // (D, P, Q above have become Δ, b, 1): + // + // Let U_n = U_n(b, 1), V_n = V_n(b, 1), and Δ = b²-4. + // An extra strong Lucas pseudoprime to base b is a composite n = 2^r s + Jacobi(Δ, n), + // where s is odd and gcd(n, 2*Δ) = 1, such that either (i) U_s ≡ 0 mod n and V_s ≡ ±2 mod n, + // or (ii) V_{2^t s} ≡ 0 mod n for some 0 ≤ t < r-1. + // + // We know gcd(n, Δ) = 1 or else we'd have found Jacobi(d, n) == 0 above. + // We know gcd(n, 2) = 1 because n is odd. + // + // Arrange s = (n - Jacobi(Δ, n)) / 2^r = (n+1) / 2^r. + s := nat(nil).add(n, natOne) + r := int(s.trailingZeroBits()) + s = s.shr(s, uint(r)) + nm2 := nat(nil).sub(n, natTwo) // n-2 + + // We apply the "almost extra strong" test, which checks the above conditions + // except for U_s ≡ 0 mod n, which allows us to avoid computing any U_k values. + // Jacobsen points out that maybe we should just do the full extra strong test: + // "It is also possible to recover U_n using Crandall and Pomerance equation 3.13: + // U_n = D^-1 (2V_{n+1} - PV_n) allowing us to run the full extra-strong test + // at the cost of a single modular inversion. This computation is easy and fast in GMP, + // so we can get the full extra-strong test at essentially the same performance as the + // almost extra strong test." + + // Compute Lucas sequence V_s(b, 1), where: + // + // V(0) = 2 + // V(1) = P + // V(k) = P V(k-1) - Q V(k-2). + // + // (Remember that due to method C above, P = b, Q = 1.) + // + // In general V(k) = α^k + β^k, where α and β are roots of x² - Px + Q. + // Crandall and Pomerance (p.147) observe that for 0 ≤ j ≤ k, + // + // V(j+k) = V(j)V(k) - V(k-j). + // + // So in particular, to quickly double the subscript: + // + // V(2k) = V(k)² - 2 + // V(2k+1) = V(k) V(k+1) - P + // + // We can therefore start with k=0 and build up to k=s in log₂(s) steps. + natP := nat(nil).setWord(p) + vk := nat(nil).setWord(2) + vk1 := nat(nil).setWord(p) + t2 := nat(nil) // temp + for i := int(s.bitLen()); i >= 0; i-- { + if s.bit(uint(i)) != 0 { + // k' = 2k+1 + // V(k') = V(2k+1) = V(k) V(k+1) - P. + t1 = t1.mul(vk, vk1) + t1 = t1.add(t1, n) + t1 = t1.sub(t1, natP) + t2, vk = t2.div(vk, t1, n) + // V(k'+1) = V(2k+2) = V(k+1)² - 2. + t1 = t1.mul(vk1, vk1) + t1 = t1.add(t1, nm2) + t2, vk1 = t2.div(vk1, t1, n) + } else { + // k' = 2k + // V(k'+1) = V(2k+1) = V(k) V(k+1) - P. + t1 = t1.mul(vk, vk1) + t1 = t1.add(t1, n) + t1 = t1.sub(t1, natP) + t2, vk1 = t2.div(vk1, t1, n) + // V(k') = V(2k) = V(k)² - 2 + t1 = t1.mul(vk, vk) + t1 = t1.add(t1, nm2) + t2, vk = t2.div(vk, t1, n) + } + } + + // Now k=s, so vk = V(s). Check V(s) ≡ ±2 (mod n). + if vk.cmp(natTwo) == 0 || vk.cmp(nm2) == 0 { + // Check U(s) ≡ 0. + // As suggested by Jacobsen, apply Crandall and Pomerance equation 3.13: + // + // U(k) = D⁻¹ (2 V(k+1) - P V(k)) + // + // Since we are checking for U(k) == 0 it suffices to check 2 V(k+1) == P V(k) mod n, + // or P V(k) - 2 V(k+1) == 0 mod n. + t1 := t1.mul(vk, natP) + t2 := t2.shl(vk1, 1) + if t1.cmp(t2) < 0 { + t1, t2 = t2, t1 + } + t1 = t1.sub(t1, t2) + t3 := vk1 // steal vk1, no longer needed below + vk1 = nil + _ = vk1 + t2, t3 = t2.div(t3, t1, n) + if len(t3) == 0 { + return true + } + } + + // Check V(2^t s) ≡ 0 mod n for some 0 ≤ t < r-1. + for t := 0; t < r-1; t++ { + if len(vk) == 0 { // vk == 0 + return true + } + // Optimization: V(k) = 2 is a fixed point for V(k') = V(k)² - 2, + // so if V(k) = 2, we can stop: we will never find a future V(k) == 0. + if len(vk) == 1 && vk[0] == 2 { // vk == 2 + return false + } + // k' = 2k + // V(k') = V(2k) = V(k)² - 2 + t1 = t1.mul(vk, vk) + t1 = t1.sub(t1, natTwo) + t2, vk = t2.div(vk, t1, n) + } + return false +} diff --git a/libgo/go/math/big/prime_test.go b/libgo/go/math/big/prime_test.go new file mode 100644 index 0000000..a2d3d18 --- /dev/null +++ b/libgo/go/math/big/prime_test.go @@ -0,0 +1,214 @@ +// Copyright 2016 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 big + +import ( + "fmt" + "strings" + "testing" + "unicode" +) + +var primes = []string{ + "2", + "3", + "5", + "7", + "11", + + "13756265695458089029", + "13496181268022124907", + "10953742525620032441", + "17908251027575790097", + + // https://golang.org/issue/638 + "18699199384836356663", + + "98920366548084643601728869055592650835572950932266967461790948584315647051443", + "94560208308847015747498523884063394671606671904944666360068158221458669711639", + + // http://primes.utm.edu/lists/small/small3.html + "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163", + "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593", + "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993", + "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", + + // ECC primes: http://tools.ietf.org/html/draft-ladd-safecurves-02 + "3618502788666131106986593281521497120414687020801267626233049500247285301239", // Curve1174: 2^251-9 + "57896044618658097711785492504343953926634992332820282019728792003956564819949", // Curve25519: 2^255-19 + "9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599", // E-382: 2^382-105 + "42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367", // Curve41417: 2^414-17 + "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", // E-521: 2^521-1 +} + +var composites = []string{ + "0", + "1", + "21284175091214687912771199898307297748211672914763848041968395774954376176754", + "6084766654921918907427900243509372380954290099172559290432744450051395395951", + "84594350493221918389213352992032324280367711247940675652888030554255915464401", + "82793403787388584738507275144194252681", + + // Arnault, "Rabin-Miller Primality Test: Composite Numbers Which Pass It", + // Mathematics of Computation, 64(209) (January 1995), pp. 335-361. + "1195068768795265792518361315725116351898245581", // strong pseudoprime to prime bases 2 through 29 + // strong pseudoprime to all prime bases up to 200 + ` + 80383745745363949125707961434194210813883768828755814583748891752229 + 74273765333652186502336163960045457915042023603208766569966760987284 + 0439654082329287387918508691668573282677617710293896977394701670823 + 0428687109997439976544144845341155872450633409279022275296229414984 + 2306881685404326457534018329786111298960644845216191652872597534901`, + + // Extra-strong Lucas pseudoprimes. https://oeis.org/A217719 + "989", + "3239", + "5777", + "10877", + "27971", + "29681", + "30739", + "31631", + "39059", + "72389", + "73919", + "75077", + "100127", + "113573", + "125249", + "137549", + "137801", + "153931", + "155819", + "161027", + "162133", + "189419", + "218321", + "231703", + "249331", + "370229", + "429479", + "430127", + "459191", + "473891", + "480689", + "600059", + "621781", + "632249", + "635627", + + "3673744903", + "3281593591", + "2385076987", + "2738053141", + "2009621503", + "1502682721", + "255866131", + "117987841", + "587861", + + "6368689", + "8725753", + "80579735209", + "105919633", +} + +func cutSpace(r rune) rune { + if unicode.IsSpace(r) { + return -1 + } + return r +} + +func TestProbablyPrime(t *testing.T) { + nreps := 20 + if testing.Short() { + nreps = 3 + } + for i, s := range primes { + p, _ := new(Int).SetString(s, 10) + if !p.ProbablyPrime(nreps) || !p.ProbablyPrime(1) || !p.ProbablyPrime(0) { + t.Errorf("#%d prime found to be non-prime (%s)", i, s) + } + } + + for i, s := range composites { + s = strings.Map(cutSpace, s) + c, _ := new(Int).SetString(s, 10) + if c.ProbablyPrime(nreps) || c.ProbablyPrime(1) || c.ProbablyPrime(0) { + t.Errorf("#%d composite found to be prime (%s)", i, s) + } + } + + // check that ProbablyPrime panics if n <= 0 + c := NewInt(11) // a prime + for _, n := range []int{-1, 0, 1} { + func() { + defer func() { + if n < 0 && recover() == nil { + t.Fatalf("expected panic from ProbablyPrime(%d)", n) + } + }() + if !c.ProbablyPrime(n) { + t.Fatalf("%v should be a prime", c) + } + }() + } +} + +func BenchmarkProbablyPrime(b *testing.B) { + p, _ := new(Int).SetString("203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", 10) + for _, n := range []int{0, 1, 5, 10, 20} { + b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) { + for i := 0; i < b.N; i++ { + p.ProbablyPrime(n) + } + }) + } + + b.Run("Lucas", func(b *testing.B) { + for i := 0; i < b.N; i++ { + p.abs.probablyPrimeLucas() + } + }) + b.Run("MillerRabinBase2", func(b *testing.B) { + for i := 0; i < b.N; i++ { + p.abs.probablyPrimeMillerRabin(1, true) + } + }) +} + +func TestMillerRabinPseudoprimes(t *testing.T) { + testPseudoprimes(t, "probablyPrimeMillerRabin", + func(n nat) bool { return n.probablyPrimeMillerRabin(1, true) && !n.probablyPrimeLucas() }, + // https://oeis.org/A001262 + []int{2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751}) +} + +func TestLucasPseudoprimes(t *testing.T) { + testPseudoprimes(t, "probablyPrimeLucas", + func(n nat) bool { return n.probablyPrimeLucas() && !n.probablyPrimeMillerRabin(1, true) }, + // https://oeis.org/A217719 + []int{989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389, 73919, 75077}) +} + +func testPseudoprimes(t *testing.T, name string, cond func(nat) bool, want []int) { + n := nat{1} + for i := 3; i < 100000; i += 2 { + n[0] = Word(i) + pseudo := cond(n) + if pseudo && (len(want) == 0 || i != want[0]) { + t.Errorf("%s(%v, base=2) = %v, want false", name, i) + } else if !pseudo && len(want) >= 1 && i == want[0] { + t.Errorf("%s(%v, base=2) = false, want true", name, i) + } + if len(want) > 0 && i == want[0] { + want = want[1:] + } + } + if len(want) > 0 { + t.Fatalf("forgot to test %v", want) + } +} diff --git a/libgo/go/math/big/rat_test.go b/libgo/go/math/big/rat_test.go index 3a06fca..afda686 100644 --- a/libgo/go/math/big/rat_test.go +++ b/libgo/go/math/big/rat_test.go @@ -382,9 +382,9 @@ func TestFloat32Distribution(t *testing.T) { 9, 11, } - var winc, einc = uint64(1), 1 // soak test (~1.5s on x86-64) - if testing.Short() { - winc, einc = 5, 15 // quick test (~60ms on x86-64) + var winc, einc = uint64(5), 15 // quick test (~60ms on x86-64) + if *long { + winc, einc = uint64(1), 1 // soak test (~1.5s on x86-64) } for _, sign := range "+-" { @@ -430,9 +430,9 @@ func TestFloat64Distribution(t *testing.T) { 9, 11, } - var winc, einc = uint64(1), 1 // soak test (~75s on x86-64) - if testing.Short() { - winc, einc = 10, 500 // quick test (~12ms on x86-64) + var winc, einc = uint64(10), 500 // quick test (~12ms on x86-64) + if *long { + winc, einc = uint64(1), 1 // soak test (~75s on x86-64) } for _, sign := range "+-" { diff --git a/libgo/go/math/big/ratconv.go b/libgo/go/math/big/ratconv.go index ef2b675..a6a401c 100644 --- a/libgo/go/math/big/ratconv.go +++ b/libgo/go/math/big/ratconv.go @@ -18,6 +18,9 @@ func ratTok(ch rune) bool { return strings.ContainsRune("+-/0123456789.eE", ch) } +var ratZero Rat +var _ fmt.Scanner = &ratZero // *Rat must implement fmt.Scanner + // Scan is a support routine for fmt.Scanner. It accepts the formats // 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent. func (z *Rat) Scan(s fmt.ScanState, ch rune) error { @@ -36,8 +39,9 @@ func (z *Rat) Scan(s fmt.ScanState, ch rune) error { // SetString sets z to the value of s and returns z and a boolean indicating // success. s can be given as a fraction "a/b" or as a floating-point number -// optionally followed by an exponent. If the operation failed, the value of -// z is undefined but the returned value is nil. +// optionally followed by an exponent. The entire string (not just a prefix) +// must be valid for success. If the operation failed, the value of z is un- +// defined but the returned value is nil. func (z *Rat) SetString(s string) (*Rat, bool) { if len(s) == 0 { return nil, false @@ -49,9 +53,13 @@ func (z *Rat) SetString(s string) (*Rat, bool) { if _, ok := z.a.SetString(s[:sep], 0); !ok { return nil, false } - s = s[sep+1:] + r := strings.NewReader(s[sep+1:]) var err error - if z.b.abs, _, _, err = z.b.abs.scan(strings.NewReader(s), 0, false); err != nil { + if z.b.abs, _, _, err = z.b.abs.scan(r, 0, false); err != nil { + return nil, false + } + // entire string must have been consumed + if _, err = r.ReadByte(); err != io.EOF { return nil, false } if len(z.b.abs) == 0 { diff --git a/libgo/go/math/big/ratconv_test.go b/libgo/go/math/big/ratconv_test.go index 35ad6cc..56ac8d7 100644 --- a/libgo/go/math/big/ratconv_test.go +++ b/libgo/go/math/big/ratconv_test.go @@ -50,6 +50,10 @@ var setStringTests = []StringTest{ {"204211327800791583.81095", "4084226556015831676219/20000", true}, {"0e9999999999", "0", true}, // issue #16176 {in: "1/0"}, + {in: "4/3/2"}, // issue 17001 + {in: "4/3/"}, + {in: "4/3."}, + {in: "4/"}, } // These are not supported by fmt.Fscanf. @@ -59,6 +63,7 @@ var setStringTests2 = []StringTest{ {"-010.", "-10", true}, {"0x10/0x20", "1/2", true}, {"0b1000/3", "8/3", true}, + {in: "4/3x"}, // TODO(gri) add more tests } @@ -139,7 +144,7 @@ func TestFloatString(t *testing.T) { } // Test inputs to Rat.SetString. The prefix "long:" causes the test -// to be skipped in --test.short mode. (The threshold is about 500us.) +// to be skipped except in -long mode. (The threshold is about 500us.) var float64inputs = []string{ // Constants plundered from strconv/testfp.txt. @@ -345,7 +350,7 @@ func isFinite(f float64) bool { func TestFloat32SpecialCases(t *testing.T) { for _, input := range float64inputs { if strings.HasPrefix(input, "long:") { - if testing.Short() { + if !*long { continue } input = input[len("long:"):] @@ -401,7 +406,7 @@ func TestFloat32SpecialCases(t *testing.T) { func TestFloat64SpecialCases(t *testing.T) { for _, input := range float64inputs { if strings.HasPrefix(input, "long:") { - if testing.Short() { + if !*long { continue } input = input[len("long:"):] diff --git a/libgo/go/math/cmplx/cmath_test.go b/libgo/go/math/cmplx/cmath_test.go index d904be8..7a5c485 100644 --- a/libgo/go/math/cmplx/cmath_test.go +++ b/libgo/go/math/cmplx/cmath_test.go @@ -759,6 +759,14 @@ func TestTanh(t *testing.T) { } } +// See issue 17577 +func TestInfiniteLoopIntanSeries(t *testing.T) { + want := Inf() + if got := Cot(0); got != want { + t.Errorf("Cot(0): got %g, want %g", got, want) + } +} + func BenchmarkAbs(b *testing.B) { for i := 0; i < b.N; i++ { Abs(complex(2.5, 3.5)) diff --git a/libgo/go/math/cmplx/example_test.go b/libgo/go/math/cmplx/example_test.go new file mode 100644 index 0000000..be87cff --- /dev/null +++ b/libgo/go/math/cmplx/example_test.go @@ -0,0 +1,30 @@ +// Copyright 2016 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. + +// +build ignore + +package cmplx_test + +import ( + "fmt" + "math" + "math/cmplx" +) + +func ExampleAbs() { + fmt.Printf("%.1f", cmplx.Abs(3+4i)) + // Output: 5.0 +} + +// ExampleExp computes Euler's identity. +func ExampleExp() { + fmt.Printf("%.1f", cmplx.Exp(1i*math.Pi)+1) + // Output: (0.0+0.0i) +} + +func ExamplePolar() { + r, theta := cmplx.Polar(2i) + fmt.Printf("r: %.1f, θ: %.1f*π", r, theta/math.Pi) + // Output: r: 2.0, θ: 0.5*π +} diff --git a/libgo/go/math/cmplx/tan.go b/libgo/go/math/cmplx/tan.go index 9485315..2990552 100644 --- a/libgo/go/math/cmplx/tan.go +++ b/libgo/go/math/cmplx/tan.go @@ -120,9 +120,9 @@ func tanSeries(z complex128) float64 { rn := 0.0 d := 0.0 for { - rn += 1 + rn++ f *= rn - rn += 1 + rn++ f *= rn x2 *= x y2 *= y @@ -130,16 +130,18 @@ func tanSeries(z complex128) float64 { t /= f d += t - rn += 1 + rn++ f *= rn - rn += 1 + rn++ f *= rn x2 *= x y2 *= y t = y2 - x2 t /= f d += t - if math.Abs(t/d) <= MACHEP { + if !(math.Abs(t/d) > MACHEP) { + // Caution: Use ! and > instead of <= for correct behavior if t/d is NaN. + // See issue 17577. break } } diff --git a/libgo/go/math/expm1.go b/libgo/go/math/expm1.go index 5a96218..a0a62d1 100644 --- a/libgo/go/math/expm1.go +++ b/libgo/go/math/expm1.go @@ -235,7 +235,7 @@ func expm1(x float64) float64 { } t := Float64frombits(uint64(0x3ff-k) << 52) // 2**-k y := x - (e + t) - y += 1 + y++ y = Float64frombits(Float64bits(y) + uint64(k)<<52) // add k to y's exponent return y } diff --git a/libgo/go/math/export_s390x_test.go b/libgo/go/math/export_s390x_test.go new file mode 100644 index 0000000..3fdbd86 --- /dev/null +++ b/libgo/go/math/export_s390x_test.go @@ -0,0 +1,14 @@ +// Copyright 2016 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 + +// Export internal functions and variable for testing. +var Log10NoVec = log10 +var CosNoVec = cos +var CoshNoVec = cosh +var SinNoVec = sin +var SinhNoVec = sinh +var TanhNoVec = tanh +var HasVX = hasVX diff --git a/libgo/go/math/gamma.go b/libgo/go/math/gamma.go index 841ec11..cc9e869 100644 --- a/libgo/go/math/gamma.go +++ b/libgo/go/math/gamma.go @@ -91,23 +91,31 @@ var _gamS = [...]float64{ } // Gamma function computed by Stirling's formula. -// The polynomial is valid for 33 <= x <= 172. -func stirling(x float64) float64 { +// The pair of results must be multiplied together to get the actual answer. +// The multiplication is left to the caller so that, if careful, the caller can avoid +// infinity for 172 <= x <= 180. +// The polynomial is valid for 33 <= x <= 172; larger values are only used +// in reciprocal and produce denormalized floats. The lower precision there +// masks any imprecision in the polynomial. +func stirling(x float64) (float64, float64) { + if x > 200 { + return Inf(1), 1 + } const ( SqrtTwoPi = 2.506628274631000502417 MaxStirling = 143.01608 ) w := 1 / x w = 1 + w*((((_gamS[0]*w+_gamS[1])*w+_gamS[2])*w+_gamS[3])*w+_gamS[4]) - y := Exp(x) + y1 := Exp(x) + y2 := 1.0 if x > MaxStirling { // avoid Pow() overflow v := Pow(x, 0.5*x-0.25) - y = v * (v / y) + y1, y2 = v, v/y1 } else { - y = Pow(x, x-0.5) / y + y1 = Pow(x, x-0.5) / y1 } - y = SqrtTwoPi * y * w - return y + return y1, SqrtTwoPi * w * y2 } // Gamma returns the Gamma function of x. @@ -125,22 +133,26 @@ func Gamma(x float64) float64 { switch { case isNegInt(x) || IsInf(x, -1) || IsNaN(x): return NaN() + case IsInf(x, 1): + return Inf(1) case x == 0: if Signbit(x) { return Inf(-1) } return Inf(1) - case x < -170.5674972726612 || x > 171.61447887182298: - return Inf(1) } q := Abs(x) p := Floor(q) if q > 33 { if x >= 0 { - return stirling(x) + y1, y2 := stirling(x) + return y1 * y2 } + // Note: x is negative but (checked above) not a negative integer, + // so x must be small enough to be in range for conversion to int64. + // If |x| were >= 2⁶³ it would have to be an integer. signgam := 1 - if ip := int(p); ip&1 == 0 { + if ip := int64(p); ip&1 == 0 { signgam = -1 } z := q - p @@ -152,7 +164,14 @@ func Gamma(x float64) float64 { if z == 0 { return Inf(signgam) } - z = Pi / (Abs(z) * stirling(q)) + sq1, sq2 := stirling(q) + absz := Abs(z) + d := absz * sq1 * sq2 + if IsInf(d, 0) { + z = Pi / absz / sq1 / sq2 + } else { + z = Pi / d + } return float64(signgam) * z } diff --git a/libgo/go/math/j0.go b/libgo/go/math/j0.go index cbef7aa..fe26791 100644 --- a/libgo/go/math/j0.go +++ b/libgo/go/math/j0.go @@ -305,20 +305,20 @@ var p0S2 = [5]float64{ } func pzero(x float64) float64 { - var p [6]float64 - var q [5]float64 + var p *[6]float64 + var q *[5]float64 if x >= 8 { - p = p0R8 - q = p0S8 + p = &p0R8 + q = &p0S8 } else if x >= 4.5454 { - p = p0R5 - q = p0S5 + p = &p0R5 + q = &p0S5 } else if x >= 2.8571 { - p = p0R3 - q = p0S3 + p = &p0R3 + q = &p0S3 } else if x >= 2 { - p = p0R2 - q = p0S2 + p = &p0R2 + q = &p0S2 } z := 1 / (x * x) r := p[0] + z*(p[1]+z*(p[2]+z*(p[3]+z*(p[4]+z*p[5])))) @@ -408,19 +408,19 @@ var q0S2 = [6]float64{ } func qzero(x float64) float64 { - var p, q [6]float64 + var p, q *[6]float64 if x >= 8 { - p = q0R8 - q = q0S8 + p = &q0R8 + q = &q0S8 } else if x >= 4.5454 { - p = q0R5 - q = q0S5 + p = &q0R5 + q = &q0S5 } else if x >= 2.8571 { - p = q0R3 - q = q0S3 + p = &q0R3 + q = &q0S3 } else if x >= 2 { - p = q0R2 - q = q0S2 + p = &q0R2 + q = &q0S2 } z := 1 / (x * x) r := p[0] + z*(p[1]+z*(p[2]+z*(p[3]+z*(p[4]+z*p[5])))) diff --git a/libgo/go/math/j1.go b/libgo/go/math/j1.go index d359d90..f1adcb6 100644 --- a/libgo/go/math/j1.go +++ b/libgo/go/math/j1.go @@ -298,20 +298,20 @@ var p1S2 = [5]float64{ } func pone(x float64) float64 { - var p [6]float64 - var q [5]float64 + var p *[6]float64 + var q *[5]float64 if x >= 8 { - p = p1R8 - q = p1S8 + p = &p1R8 + q = &p1S8 } else if x >= 4.5454 { - p = p1R5 - q = p1S5 + p = &p1R5 + q = &p1S5 } else if x >= 2.8571 { - p = p1R3 - q = p1S3 + p = &p1R3 + q = &p1S3 } else if x >= 2 { - p = p1R2 - q = p1S2 + p = &p1R2 + q = &p1S2 } z := 1 / (x * x) r := p[0] + z*(p[1]+z*(p[2]+z*(p[3]+z*(p[4]+z*p[5])))) @@ -401,19 +401,19 @@ var q1S2 = [6]float64{ } func qone(x float64) float64 { - var p, q [6]float64 + var p, q *[6]float64 if x >= 8 { - p = q1R8 - q = q1S8 + p = &q1R8 + q = &q1S8 } else if x >= 4.5454 { - p = q1R5 - q = q1S5 + p = &q1R5 + q = &q1S5 } else if x >= 2.8571 { - p = q1R3 - q = q1S3 + p = &q1R3 + q = &q1S3 } else if x >= 2 { - p = q1R2 - q = q1S2 + p = &q1R2 + q = &q1S2 } z := 1 / (x * x) r := p[0] + z*(p[1]+z*(p[2]+z*(p[3]+z*(p[4]+z*p[5])))) diff --git a/libgo/go/math/jn.go b/libgo/go/math/jn.go index 721112f..3422782 100644 --- a/libgo/go/math/jn.go +++ b/libgo/go/math/jn.go @@ -174,7 +174,7 @@ func Jn(n int, x float64) float64 { q1 := w*z - 1 k := 1 for q1 < 1e9 { - k += 1 + k++ z += h q0, q1 = q1, z*q1-q0 } diff --git a/libgo/go/math/log1p.go b/libgo/go/math/log1p.go index 6834cae..ef1c7de 100644 --- a/libgo/go/math/log1p.go +++ b/libgo/go/math/log1p.go @@ -173,7 +173,7 @@ func log1p(x float64) float64 { if iu < 0x0006a09e667f3bcd { // mantissa of Sqrt(2) u = Float64frombits(iu | 0x3ff0000000000000) // normalize u } else { - k += 1 + k++ u = Float64frombits(iu | 0x3fe0000000000000) // normalize u/2 iu = (0x0010000000000000 - iu) >> 2 } @@ -185,10 +185,9 @@ func log1p(x float64) float64 { if f == 0 { if k == 0 { return 0 - } else { - c += float64(k) * Ln2Lo - return float64(k)*Ln2Hi + c } + c += float64(k) * Ln2Lo + return float64(k)*Ln2Hi + c } R = hfsq * (1.0 - 0.66666666666666666*f) // avoid division if k == 0 { diff --git a/libgo/go/math/rand/gen_cooked.go b/libgo/go/math/rand/gen_cooked.go new file mode 100644 index 0000000..567b7a8 --- /dev/null +++ b/libgo/go/math/rand/gen_cooked.go @@ -0,0 +1,89 @@ +// 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. + +// +build ignore + +// This program computes the value of rng_cooked in rng.go, +// which is used for seeding all instances of rand.Source. +// a 64bit and a 63bit version of the array is printed to +// the standard output. + +package main + +import "fmt" + +const ( + length = 607 + tap = 273 + mask = (1 << 63) - 1 + a = 48271 + m = (1 << 31) - 1 + q = 44488 + r = 3399 +) + +var ( + rngVec [length]int64 + rngTap, rngFeed int +) + +func seedrand(x int32) int32 { + hi := x / q + lo := x % q + x = a*lo - r*hi + if x < 0 { + x += m + } + return x +} + +func srand(seed int32) { + rngTap = 0 + rngFeed = length - tap + seed %= m + if seed < 0 { + seed += m + } else if seed == 0 { + seed = 89482311 + } + x := seed + for i := -20; i < length; i++ { + x = seedrand(x) + if i >= 0 { + var u int64 + u = int64(x) << 20 + x = seedrand(x) + u ^= int64(x) << 10 + x = seedrand(x) + u ^= int64(x) + rngVec[i] = u + } + } +} + +func vrand() int64 { + rngTap-- + if rngTap < 0 { + rngTap += length + } + rngFeed-- + if rngFeed < 0 { + rngFeed += length + } + x := (rngVec[rngFeed] + rngVec[rngTap]) + rngVec[rngFeed] = x + return x +} + +func main() { + srand(1) + for i := uint64(0); i < 7.8e12; i++ { + vrand() + } + fmt.Printf("rngVec after 7.8e12 calls to vrand:\n%#v\n", rngVec) + for i := range rngVec { + rngVec[i] &= mask + } + fmt.Printf("lower 63bit of rngVec after 7.8e12 calls to vrand:\n%#v\n", rngVec) +} diff --git a/libgo/go/math/rand/race_test.go b/libgo/go/math/rand/race_test.go index 48f6c29..186c716 100644 --- a/libgo/go/math/rand/race_test.go +++ b/libgo/go/math/rand/race_test.go @@ -33,6 +33,7 @@ func TestConcurrent(t *testing.T) { seed += int64(Int63n(Int63())) seed += int64(NormFloat64()) seed += int64(Uint32()) + seed += int64(Uint64()) for _, p := range Perm(10) { seed += int64(p) } diff --git a/libgo/go/math/rand/rand.go b/libgo/go/math/rand/rand.go index dd8d43c..9fe1cbd 100644 --- a/libgo/go/math/rand/rand.go +++ b/libgo/go/math/rand/rand.go @@ -23,7 +23,20 @@ type Source interface { Seed(seed int64) } +// A Source64 is a Source that can also generate +// uniformly-distributed pseudo-random uint64 values in +// the range [0, 1<<64) directly. +// If a Rand r's underlying Source s implements Source64, +// then r.Uint64 returns the result of one call to s.Uint64 +// instead of making two calls to s.Int63. +type Source64 interface { + Source + Uint64() uint64 +} + // NewSource returns a new pseudo-random Source seeded with the given value. +// Unlike the default Source used by top-level functions, this source is not +// safe for concurrent use by multiple goroutines. func NewSource(seed int64) Source { var rng rngSource rng.Seed(seed) @@ -33,6 +46,7 @@ func NewSource(seed int64) Source { // A Rand is a source of random numbers. type Rand struct { src Source + s64 Source64 // non-nil if src is source64 // readVal contains remainder of 63-bit integer used for bytes // generation during most recent Read call. @@ -46,7 +60,10 @@ type Rand struct { // New returns a new Rand that uses random values from src // to generate other random values. -func New(src Source) *Rand { return &Rand{src: src} } +func New(src Source) *Rand { + s64, _ := src.(Source64) + return &Rand{src: src, s64: s64} +} // Seed uses the provided seed value to initialize the generator to a deterministic state. // Seed should not be called concurrently with any other Rand method. @@ -66,6 +83,14 @@ func (r *Rand) Int63() int64 { return r.src.Int63() } // Uint32 returns a pseudo-random 32-bit value as a uint32. func (r *Rand) Uint32() uint32 { return uint32(r.Int63() >> 31) } +// Uint64 returns a pseudo-random 64-bit value as a uint64. +func (r *Rand) Uint64() uint64 { + if r.s64 != nil { + return r.s64.Uint64() + } + return uint64(r.Int63())>>31 | uint64(r.Int63())<<32 +} + // Int31 returns a non-negative pseudo-random 31-bit integer as an int32. func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) } @@ -207,7 +232,7 @@ func read(p []byte, int63 func() int64, readVal *int64, readPos *int8) (n int, e * Top-level convenience functions */ -var globalRand = New(&lockedSource{src: NewSource(1)}) +var globalRand = New(&lockedSource{src: NewSource(1).(Source64)}) // Seed uses the provided seed value to initialize the default Source to a // deterministic state. If Seed is not called, the generator behaves as @@ -224,6 +249,10 @@ func Int63() int64 { return globalRand.Int63() } // from the default Source. func Uint32() uint32 { return globalRand.Uint32() } +// Uint64 returns a pseudo-random 64-bit value as a uint64 +// from the default Source. +func Uint64() uint64 { return globalRand.Uint64() } + // Int31 returns a non-negative pseudo-random 31-bit integer as an int32 // from the default Source. func Int31() int32 { return globalRand.Int31() } @@ -286,7 +315,7 @@ func ExpFloat64() float64 { return globalRand.ExpFloat64() } type lockedSource struct { lk sync.Mutex - src Source + src Source64 } func (r *lockedSource) Int63() (n int64) { @@ -296,6 +325,13 @@ func (r *lockedSource) Int63() (n int64) { return } +func (r *lockedSource) Uint64() (n uint64) { + r.lk.Lock() + n = r.src.Uint64() + r.lk.Unlock() + return +} + func (r *lockedSource) Seed(seed int64) { r.lk.Lock() r.src.Seed(seed) diff --git a/libgo/go/math/rand/rand_test.go b/libgo/go/math/rand/rand_test.go index 6f31279..bf509e0 100644 --- a/libgo/go/math/rand/rand_test.go +++ b/libgo/go/math/rand/rand_test.go @@ -328,13 +328,26 @@ func TestExpTables(t *testing.T) { } } +func hasSlowFloatingPoint() bool { + switch runtime.GOARCH { + case "arm": + return os.Getenv("GOARM") == "5" + case "mips", "mipsle", "mips64", "mips64le": + // Be conservative and assume that all mips boards + // have emulated floating point. + // TODO: detect what it actually has. + return true + } + return false +} + func TestFloat32(t *testing.T) { // For issue 6721, the problem came after 7533753 calls, so check 10e6. num := int(10e6) // But do the full amount only on builders (not locally). // But ARM5 floating point emulation is slow (Issue 10749), so // do less for that builder: - if testing.Short() && (testenv.Builder() == "" || runtime.GOARCH == "arm" && os.Getenv("GOARM") == "5") { + if testing.Short() && (testenv.Builder() == "" || hasSlowFloatingPoint()) { num /= 100 // 1.72 seconds instead of 172 seconds } diff --git a/libgo/go/math/rand/regress_test.go b/libgo/go/math/rand/regress_test.go index 4dd965c..e31e6c5 100644 --- a/libgo/go/math/rand/regress_test.go +++ b/libgo/go/math/rand/regress_test.go @@ -381,4 +381,24 @@ var regressGolden = []interface{}{ uint32(75079301), // Uint32() uint32(3380456901), // Uint32() uint32(3433369789), // Uint32() + uint64(8717895732742165505), // Uint64() + uint64(2259404117704393152), // Uint64() + uint64(6050128673802995827), // Uint64() + uint64(9724605487393973602), // Uint64() + uint64(12613765599614152010), // Uint64() + uint64(11893357769247901871), // Uint64() + uint64(1774932891286980153), // Uint64() + uint64(15267744271532198264), // Uint64() + uint64(17498302081433670737), // Uint64() + uint64(1543572285742637646), // Uint64() + uint64(11885104867954719224), // Uint64() + uint64(17548432336275752516), // Uint64() + uint64(7837839688282259259), // Uint64() + uint64(2518412263346885298), // Uint64() + uint64(5617773211005988520), // Uint64() + uint64(11562935753659892057), // Uint64() + uint64(16368296284793757383), // Uint64() + uint64(161231572858529631), // Uint64() + uint64(16482847956365694147), // Uint64() + uint64(16596477517051940556), // Uint64() } diff --git a/libgo/go/math/rand/rng.go b/libgo/go/math/rand/rng.go index 947c49f..f922417 100644 --- a/libgo/go/math/rand/rng.go +++ b/libgo/go/math/rand/rng.go @@ -23,161 +23,159 @@ const ( ) var ( - // cooked random numbers - // the state of the rng - // after 780e10 iterations + // Used for seeding. See gen_cooked.go for details. rng_cooked [_LEN]int64 = [...]int64{ - 5041579894721019882, 4646389086726545243, 1395769623340756751, 5333664234075297259, - 2875692520355975054, 9033628115061424579, 7143218595135194537, 4812947590706362721, - 7937252194349799378, 5307299880338848416, 8209348851763925077, 2115741599318814044, - 4593015457530856296, 8140875735541888011, 3319429241265089026, 8619815648190321034, - 1727074043483619500, 113108499721038619, 4569519971459345583, 5062833859075314731, - 2387618771259064424, 2716131344356686112, 6559392774825876886, 7650093201692370310, - 7684323884043752161, 257867835996031390, 6593456519409015164, 271327514973697897, - 2789386447340118284, 1065192797246149621, 3344507881999356393, 4459797941780066633, - 7465081662728599889, 1014950805555097187, 4449440729345990775, 3481109366438502643, + -4181792142133755926, -4576982950128230565, 1395769623340756751, 5333664234075297259, + -6347679516498800754, 9033628115061424579, 7143218595135194537, 4812947590706362721, + 7937252194349799378, 5307299880338848416, 8209348851763925077, -7107630437535961764, + 4593015457530856296, 8140875735541888011, -5903942795589686782, -603556388664454774, + -7496297993371156308, 113108499721038619, 4569519971459345583, -4160538177779461077, + -6835753265595711384, -6507240692498089696, 6559392774825876886, 7650093201692370310, + 7684323884043752161, -8965504200858744418, -2629915517445760644, 271327514973697897, + -6433985589514657524, 1065192797246149621, 3344507881999356393, -4763574095074709175, + 7465081662728599889, 1014950805555097187, -4773931307508785033, -5742262670416273165, 2418672789110888383, 5796562887576294778, 4484266064449540171, 3738982361971787048, - 4523597184512354423, 10530508058128498, 8633833783282346118, 2625309929628791628, - 8660405965245884302, 10162832508971942, 6540714680961817391, 7031802312784620857, - 6240911277345944669, 831864355460801054, 8004434137542152891, 2116287251661052151, + -4699774852342421385, 10530508058128498, -589538253572429690, -6598062107225984180, + 8660405965245884302, 10162832508971942, -2682657355892958417, 7031802312784620857, + 6240911277345944669, 831864355460801054, -1218937899312622917, 2116287251661052151, 2202309800992166967, 9161020366945053561, 4069299552407763864, 4936383537992622449, - 457351505131524928, 342195045928179354, 2847771682816600509, 2068020115986376518, - 4368649989588021065, 887231587095185257, 5563591506886576496, 6816225200251950296, - 5616972787034086048, 8471809303394836566, 1686575021641186857, 4045484338074262002, - 4244156215201778923, 7848217333783577387, 5632136521049761902, 833283142057835272, - 9029726508369077193, 3243583134664087292, 4316371101804477087, 8937849979965997980, - 6446940406810434101, 1679342092332374735, 6050638460742422078, 6993520719509581582, - 7640877852514293609, 5881353426285907985, 812786550756860885, 4541845584483343330, - 2725470216277009086, 4980675660146853729, 5210769080603236061, 8894283318990530821, - 6326442804750084282, 1495812843684243920, 7069751578799128019, 7370257291860230865, - 6756929275356942261, 4706794511633873654, 7824520467827898663, 8549875090542453214, - 33650829478596156, 1328918435751322643, 7297902601803624459, 1011190183918857495, - 2238025036817854944, 5147159997473910359, 896512091560522982, 2659470849286379941, - 6097729358393448602, 1731725986304753684, 4106255841983812711, 8327155210721535508, - 8477511620686074402, 5803876044675762232, 8435417780860221662, 5988852856651071244, - 4715837297103951910, 7566171971264485114, 505808562678895611, 5070098180695063370, - 842110666775871513, 572156825025677802, 1791881013492340891, 3393267094866038768, - 3778721850472236509, 2352769483186201278, 1292459583847367458, 8897907043675088419, - 5781809037144163536, 2733958794029492513, 5092019688680754699, 8996124554772526841, - 4234737173186232084, 5027558287275472836, 4635198586344772304, 8687338893267139351, - 5907508150730407386, 784756255473944452, 972392927514829904, 5422057694808175112, - 5158420642969283891, 9048531678558643225, 2407211146698877100, 7583282216521099569, - 3940796514530962282, 3341174631045206375, 3095313889586102949, 7405321895688238710, - 5832080132947175283, 7890064875145919662, 8184139210799583195, 1149859861409226130, - 1464597243840211302, 4641648007187991873, 3516491885471466898, 956288521791657692, + 457351505131524928, -8881176990926596454, -6375600354038175299, -7155351920868399290, + 4368649989588021065, 887231587095185257, -3659780529968199312, -2407146836602825512, + 5616972787034086048, -751562733459939242, 1686575021641186857, -5177887698780513806, + -4979215821652996885, -1375154703071198421, 5632136521049761902, -8390088894796940536, + -193645528485698615, -5979788902190688516, -4907000935050298721, -285522056888777828, + -2776431630044341707, 1679342092332374735, 6050638460742422078, -2229851317345194226, + -1582494184340482199, 5881353426285907985, 812786550756860885, 4541845584483343330, + -6497901820577766722, 4980675660146853729, -4012602956251539747, -329088717864244987, + -2896929232104691526, 1495812843684243920, -2153620458055647789, 7370257291860230865, + -2466442761497833547, 4706794511633873654, -1398851569026877145, 8549875090542453214, + -9189721207376179652, -7894453601103453165, 7297902601803624459, 1011190183918857495, + -6985347000036920864, 5147159997473910359, -8326859945294252826, 2659470849286379941, + 6097729358393448602, -7491646050550022124, -5117116194870963097, -896216826133240300, + -745860416168701406, 5803876044675762232, -787954255994554146, -3234519180203704564, + -4507534739750823898, -1657200065590290694, 505808562678895611, -4153273856159712438, + -8381261370078904295, 572156825025677802, 1791881013492340891, 3393267094866038768, + -5444650186382539299, 2352769483186201278, -7930912453007408350, -325464993179687389, + -3441562999710612272, -6489413242825283295, 5092019688680754699, -227247482082248967, + 4234737173186232084, 5027558287275472836, 4635198586344772304, -536033143587636457, + 5907508150730407386, -8438615781380831356, 972392927514829904, -3801314342046600696, + -4064951393885491917, -174840358296132583, 2407211146698877100, -1640089820333676239, + 3940796514530962282, -5882197405809569433, 3095313889586102949, -1818050141166537098, + 5832080132947175283, 7890064875145919662, 8184139210799583195, -8073512175445549678, + -7758774793014564506, -4581724029666783935, 3516491885471466898, -8267083515063118116, 6657089965014657519, 5220884358887979358, 1796677326474620641, 5340761970648932916, 1147977171614181568, 5066037465548252321, 2574765911837859848, 1085848279845204775, - 3350107529868390359, 6116438694366558490, 2107701075971293812, 1803294065921269267, - 2469478054175558874, 7368243281019965984, 3791908367843677526, 185046971116456637, - 2257095756513439648, 7217693971077460129, 909049953079504259, 7196649268545224266, - 5637660345400869599, 3955544945427965183, 8057528650917418961, 4139268440301127643, - 6621926588513568059, 1373361136802681441, 6527366231383600011, 3507654575162700890, - 9202058512774729859, 1954818376891585542, 6640380907130175705, 8299563319178235687, - 3901867355218954373, 7046310742295574065, 6847195391333990232, 1572638100518868053, - 8850422670118399721, 3631909142291992901, 5158881091950831288, 2882958317343121593, - 4763258931815816403, 6280052734341785344, 4243789408204964850, 2043464728020827976, - 6545300466022085465, 4562580375758598164, 5495451168795427352, 1738312861590151095, - 553004618757816492, 6895160632757959823, 8233623922264685171, 7139506338801360852, - 8550891222387991669, 5535668688139305547, 2430933853350256242, 5401941257863201076, - 8159640039107728799, 6157493831600770366, 7632066283658143750, 6308328381617103346, + -5873264506986385449, 6116438694366558490, 2107701075971293812, -7420077970933506541, + 2469478054175558874, -1855128755834809824, -5431463669011098282, -9038325065738319171, + -6966276280341336160, 7217693971077460129, -8314322083775271549, 7196649268545224266, + -3585711691453906209, -5267827091426810625, 8057528650917418961, -5084103596553648165, + -2601445448341207749, -7850010900052094367, 6527366231383600011, 3507654575162700890, + 9202058512774729859, 1954818376891585542, -2582991129724600103, 8299563319178235687, + -5321504681635821435, 7046310742295574065, -2376176645520785576, -7650733936335907755, + 8850422670118399721, 3631909142291992901, 5158881091950831288, -6340413719511654215, + 4763258931815816403, 6280052734341785344, -4979582628649810958, 2043464728020827976, + -2678071570832690343, 4562580375758598164, 5495451168795427352, -7485059175264624713, + 553004618757816492, 6895160632757959823, -989748114590090637, 7139506338801360852, + -672480814466784139, 5535668688139305547, 2430933853350256242, -3821430778991574732, + -1063731997747047009, -3065878205254005442, 7632066283658143750, 6308328381617103346, 3681878764086140361, 3289686137190109749, 6587997200611086848, 244714774258135476, - 4079788377417136100, 8090302575944624335, 2945117363431356361, 864324395848741045, - 3009039260312620700, 8430027460082534031, 401084700045993341, 7254622446438694921, - 4707864159563588614, 5640248530963493951, 5982507712689997893, 3315098242282210105, - 5503847578771918426, 3941971367175193882, 8118566580304798074, 3839261274019871296, - 7062410411742090847, 741381002980207668, 6027994129690250817, 2497829994150063930, - 6251390334426228834, 1368930247903518833, 8809096399316380241, 6492004350391900708, - 2462145737463489636, 404828418920299174, 4153026434231690595, 261785715255475940, - 5464715384600071357, 592710404378763017, 6764129236657751224, 8513655718539357449, - 5820343663801914208, 385298524683789911, 5224135003438199467, 6303131641338802145, - 7150122561309371392, 368107899140673753, 3115186834558311558, 2915636353584281051, + -5143583659437639708, 8090302575944624335, 2945117363431356361, -8359047641006034763, + 3009039260312620700, -793344576772241777, 401084700045993341, -1968749590416080887, + 4707864159563588614, -3583123505891281857, -3240864324164777915, -5908273794572565703, + -3719524458082857382, -5281400669679581926, 8118566580304798074, 3839261274019871296, + 7062410411742090847, -8481991033874568140, 6027994129690250817, -6725542042704711878, + -2971981702428546974, -7854441788951256975, 8809096399316380241, 6492004350391900708, + 2462145737463489636, -8818543617934476634, -5070345602623085213, -8961586321599299868, + -3758656652254704451, -8630661632476012791, 6764129236657751224, -709716318315418359, + -3403028373052861600, -8838073512170985897, -3999237033416576341, -2920240395515973663, + -2073249475545404416, 368107899140673753, -6108185202296464250, -6307735683270494757, 4782583894627718279, 6718292300699989587, 8387085186914375220, 3387513132024756289, - 4654329375432538231, 8930667561363381602, 5374373436876319273, 7623042350483453954, - 7725442901813263321, 9186225467561587250, 4091027289597503355, 2357631606492579800, - 2530936820058611833, 1636551876240043639, 5564664674334965799, 1452244145334316253, - 2061642381019690829, 1279580266495294036, 9108481583171221009, 6023278686734049809, - 5007630032676973346, 2153168792952589781, 6720334534964750538, 6041546491134794105, - 3433922409283786309, 2285479922797300912, 3110614940896576130, 6366559590722842893, - 5418791419666136509, 7163298419643543757, 4891138053923696990, 580618510277907015, - 1684034065251686769, 4429514767357295841, 330346578555450005, 1119637995812174675, - 7177515271653460134, 4589042248470800257, 7693288629059004563, 143607045258444228, - 246994305896273627, 866417324803099287, 6473547110565816071, 3092379936208876896, - 2058427839513754051, 5133784708526867938, 8785882556301281247, 6149332666841167611, - 8585842181454472135, 6137678347805511274, 2070447184436970006, 5708223427705576541, - 5999657892458244504, 4358391411789012426, 325123008708389849, 6837621693887290924, - 4843721905315627004, 6010651222149276415, 5398352198963874652, 4602025990114250980, - 1044646352569048800, 9106614159853161675, 829256115228593269, 4919284369102997000, - 2681532557646850893, 3681559472488511871, 5307999518958214035, 6334130388442829274, - 2658708232916537604, 1163313865052186287, 581945337509520675, 3648778920718647903, - 4423673246306544414, 1620799783996955743, 220828013409515943, 8150384699999389761, - 4287360518296753003, 4590000184845883843, 5513660857261085186, 6964829100392774275, - 478991688350776035, 8746140185685648781, 228500091334420247, 1356187007457302238, - 3019253992034194581, 3152601605678500003, 430152752706002213, 5559581553696971176, - 4916432985369275664, 663574931734554391, 3420773838927732076, 2868348622579915573, - 1999319134044418520, 3328689518636282723, 2587672709781371173, 1517255313529399333, - 3092343956317362483, 3662252519007064108, 972445599196498113, 7664865435875959367, - 1708913533482282562, 6917817162668868494, 3217629022545312900, 2570043027221707107, - 8739788839543624613, 2488075924621352812, 4694002395387436668, 4559628481798514356, + 4654329375432538231, -292704475491394206, -3848998599978456535, 7623042350483453954, + 7725442901813263321, 9186225467561587250, -5132344747257272453, -6865740430362196008, + 2530936820058611833, 1636551876240043639, -3658707362519810009, 1452244145334316253, + -7161729655835084979, -7943791770359481772, 9108481583171221009, -3200093350120725999, + 5007630032676973346, 2153168792952589781, 6720334534964750538, -3181825545719981703, + 3433922409283786309, 2285479922797300912, 3110614940896576130, -2856812446131932915, + -3804580617188639299, 7163298419643543757, 4891138053923696990, 580618510277907015, + 1684034065251686769, 4429514767357295841, -8893025458299325803, -8103734041042601133, + 7177515271653460134, 4589042248470800257, -1530083407795771245, 143607045258444228, + 246994305896273627, -8356954712051676521, 6473547110565816071, 3092379936208876896, + 2058427839513754051, -4089587328327907870, 8785882556301281247, -3074039370013608197, + -637529855400303673, 6137678347805511274, -7152924852417805802, 5708223427705576541, + -3223714144396531304, 4358391411789012426, 325123008708389849, 6837621693887290924, + 4843721905315627004, -3212720814705499393, -3825019837890901156, 4602025990114250980, + 1044646352569048800, 9106614159853161675, -8394115921626182539, -4304087667751778808, + 2681532557646850893, 3681559472488511871, -3915372517896561773, -2889241648411946534, + -6564663803938238204, -8060058171802589521, 581945337509520675, 3648778920718647903, + -4799698790548231394, -7602572252857820065, 220828013409515943, -1072987336855386047, + 4287360518296753003, -4633371852008891965, 5513660857261085186, -2258542936462001533, + -8744380348503999773, 8746140185685648781, 228500091334420247, 1356187007457302238, + 3019253992034194581, 3152601605678500003, -8793219284148773595, 5559581553696971176, + 4916432985369275664, -8559797105120221417, -5802598197927043732, 2868348622579915573, + -7224052902810357288, -5894682518218493085, 2587672709781371173, -7706116723325376475, + 3092343956317362483, -5561119517847711700, 972445599196498113, -1558506600978816441, + 1708913533482282562, -2305554874185907314, -6005743014309462908, -6653329009633068701, + -483583197311151195, 2488075924621352812, -4529369641467339140, -4663743555056261452, 2997203966153298104, 1282559373026354493, 240113143146674385, 8665713329246516443, - 628141331766346752, 4571950817186770476, 1472811188152235408, 7596648026010355826, - 6091219417754424743, 7834161864828164065, 7103445518877254909, 4390861237357459201, - 4442653864240571734, 8903482404847331368, 622261699494173647, 6037261250297213248, - 504404948065709118, 7275215526217113061, 1011176780856001400, 2194750105623461063, - 2623071828615234808, 5157313728073836108, 3738405111966602044, 2539767524076729570, - 2467284396349269342, 5256026990536851868, 7841086888628396109, 6640857538655893162, - 1202087339038317498, 2113514992440715978, 7534350895342931403, 4925284734898484745, - 5145623771477493805, 8225140880134972332, 2719520354384050532, 9132346697815513771, - 4332154495710163773, 7137789594094346916, 6994721091344268833, 6667228574869048934, - 655440045726677499, 59934747298466858, 6124974028078036405, 8957774780655365418, - 2332206071942466437, 1701056712286369627, 3154897383618636503, 1637766181387607527, - 2460521277767576533, 197309393502684135, 643677854385267315, 2543179307861934850, - 4350769010207485119, 4754652089410667672, 2015595502641514512, 7999059458976458608, - 4287946071480840813, 8362686366770308971, 6486469209321732151, 3617727845841796026, - 7554353525834302244, 4450022655153542367, 1605195740213535749, 5327014565305508387, - 4626575813550328320, 2692222020597705149, 241045573717249868, 5098046974627094010, - 7916882295460730264, 884817090297530579, 5329160409530630596, 7790979528857726136, - 4955070238059373407, 4918537275422674302, 3008076183950404629, 3007769226071157901, - 2470346235617803020, 8928702772696731736, 7856187920214445904, 4474874585391974885, - 7900176660600710914, 2140571127916226672, 2425445057265199971, 2486055153341847830, - 4186670094382025798, 1883939007446035042, 8808666044074867985, 3734134241178479257, - 4065968871360089196, 6953124200385847784, 1305686814738899057, 1637739099014457647, - 3656125660947993209, 3966759634633167020, 3106378204088556331, 6328899822778449810, - 4565385105440252958, 1979884289539493806, 2331793186920865425, 3783206694208922581, - 8464961209802336085, 2843963751609577687, 3030678195484896323, 4793717574095772604, + 628141331766346752, -4651421219668005332, -7750560848702540400, 7596648026010355826, + -3132152619100351065, 7834161864828164065, 7103445518877254909, 4390861237357459201, + -4780718172614204074, -319889632007444440, 622261699494173647, -3186110786557562560, + -8718967088789066690, -1948156510637662747, -8212195255998774408, -7028621931231314745, + 2623071828615234808, -4066058308780939700, -5484966924888173764, -6683604512778046238, + -6756087640505506466, 5256026990536851868, 7841086888628396109, 6640857538655893162, + -8021284697816458310, -7109857044414059830, -1689021141511844405, -4298087301956291063, + -4077748265377282003, -998231156719803476, 2719520354384050532, 9132346697815513771, + 4332154495710163773, -2085582442760428892, 6994721091344268833, -2556143461985726874, + -8567931991128098309, 59934747298466858, -3098398008776739403, -265597256199410390, + 2332206071942466437, -7522315324568406181, 3154897383618636503, -7585605855467168281, + -6762850759087199275, 197309393502684135, -8579694182469508493, 2543179307861934850, + 4350769010207485119, -4468719947444108136, -7207776534213261296, -1224312577878317200, + 4287946071480840813, 8362686366770308971, 6486469209321732151, -5605644191012979782, + -1669018511020473564, 4450022655153542367, -7618176296641240059, -3896357471549267421, + -4596796223304447488, -6531150016257070659, -8982326463137525940, -4125325062227681798, + -1306489741394045544, -8338554946557245229, 5329160409530630596, 7790979528857726136, + 4955070238059373407, -4304834761432101506, -6215295852904371179, 3007769226071157901, + -6753025801236972788, 8928702772696731736, 7856187920214445904, -4748497451462800923, + 7900176660600710914, -7082800908938549136, -6797926979589575837, -6737316883512927978, + 4186670094382025798, 1883939007446035042, -414705992779907823, 3734134241178479257, + 4065968871360089196, 6953124200385847784, -7917685222115876751, -7585632937840318161, + -5567246375906782599, -5256612402221608788, 3106378204088556331, -2894472214076325998, + 4565385105440252958, 1979884289539493806, -6891578849933910383, 3783206694208922581, + 8464961209802336085, 2843963751609577687, 3030678195484896323, -4429654462759003204, 4459239494808162889, 402587895800087237, 8057891408711167515, 4541888170938985079, - 1042662272908816815, 5557303057122568958, 2647678726283249984, 2144477441549833761, - 5806352215355387087, 7117771003473903623, 5916597177708541638, 462597715452321361, - 8833658097025758785, 5970273481425315300, 563813119381731307, 2768349550652697015, - 1598828206250873866, 5206393647403558110, 6235043485709261823, 3152217402014639496, - 8469693267274066490, 125672920241807416, 5311079624024060938, 6663754932310491587, - 8736848295048751716, 4488039774992061878, 5923302823487327109, 140891791083103236, - 7414942793393574290, 7990420780896957397, 4317817392807076702, 3625184369705367340, - 2740722765288122703, 5743100009702758344, 5997898640509039159, 8854493341352484163, - 5242208035432907801, 701338899890987198, 7609280429197514109, 3020985755112334161, - 6651322707055512866, 2635195723621160615, 5144520864246028816, 1035086515727829828, - 1567242097116389047, 8172389260191636581, 6337820351429292273, 2163012566996458925, - 2743190902890262681, 1906367633221323427, 6011544915663598137, 5932255307352610768, - 2241128460406315459, 895504896216695588, 3094483003111372717, 4583857460292963101, - 9079887171656594975, 8839289181930711403, 5762740387243057873, 4225072055348026230, - 1838220598389033063, 3801620336801580414, 8823526620080073856, 1776617605585100335, - 7899055018877642622, 5421679761463003041, 5521102963086275121, 4248279443559365898, - 8735487530905098534, 1760527091573692978, 7142485049657745894, 8222656872927218123, - 4969531564923704323, 3394475942196872480, 6424174453260338141, 359248545074932887, - 3273651282831730598, 6797106199797138596, 3030918217665093212, 145600834617314036, - 6036575856065626233, 740416251634527158, 7080427635449935582, 6951781370868335478, - 399922722363687927, 294902314447253185, 7844950936339178523, 880320858634709042, - 6192655680808675579, 411604686384710388, 9026808440365124461, 6440783557497587732, + 1042662272908816815, -3666068979732206850, 2647678726283249984, 2144477441549833761, + -3417019821499388721, -2105601033380872185, 5916597177708541638, -8760774321402454447, + 8833658097025758785, 5970273481425315300, 563813119381731307, -6455022486202078793, + 1598828206250873866, -4016978389451217698, -2988328551145513985, -6071154634840136312, + 8469693267274066490, 125672920241807416, -3912292412830714870, -2559617104544284221, + -486523741806024092, -4735332261862713930, 5923302823487327109, -9082480245771672572, + -1808429243461201518, 7990420780896957397, 4317817392807076702, 3625184369705367340, + -6482649271566653105, -3480272027152017464, -3225473396345736649, -368878695502291645, + -3981164001421868007, -8522033136963788610, 7609280429197514109, 3020985755112334161, + -2572049329799262942, 2635195723621160615, 5144520864246028816, -8188285521126945980, + 1567242097116389047, 8172389260191636581, -2885551685425483535, -7060359469858316883, + -6480181133964513127, -7317004403633452381, 6011544915663598137, 5932255307352610768, + 2241128460406315459, -8327867140638080220, 3094483003111372717, 4583857460292963101, + 9079887171656594975, -384082854924064405, -3460631649611717935, 4225072055348026230, + -7385151438465742745, 3801620336801580414, -399845416774701952, -7446754431269675473, + 7899055018877642622, 5421679761463003041, 5521102963086275121, -4975092593295409910, + 8735487530905098534, -7462844945281082830, -2080886987197029914, -1000715163927557685, + -4253840471931071485, -5828896094657903328, 6424174453260338141, 359248545074932887, + -5949720754023045210, -2426265837057637212, 3030918217665093212, -9077771202237461772, + -3186796180789149575, 740416251634527158, -2142944401404840226, 6951781370868335478, + 399922722363687927, -8928469722407522623, -1378421100515597285, -8343051178220066766, + -3030716356046100229, -8811767350470065420, 9026808440365124461, 6440783557497587732, 4615674634722404292, 539897290441580544, 2096238225866883852, 8751955639408182687, - 1907224908052289603, 7381039757301768559, 6157238513393239656, 7749994231914157575, + -7316147128802486205, 7381039757301768559, 6157238513393239656, -1473377804940618233, 8629571604380892756, 5280433031239081479, 7101611890139813254, 2479018537985767835, - 7169176924412769570, 7942066497793203302, 1357759729055557688, 2278447439451174845, - 3625338785743880657, 6477479539006708521, 8976185375579272206, 5511371554711836120, + 7169176924412769570, -1281305539061572506, -7865612307799218120, 2278447439451174845, + 3625338785743880657, 6477479539006708521, 8976185375579272206, -3712000482142939688, 1326024180520890843, 7537449876596048829, 5464680203499696154, 3189671183162196045, - 6346751753565857109, 241159987320630307, 3095793449658682053, 8978332846736310159, - 2902794662273147216, 7208698530190629697, 7276901792339343736, 1732385229314443140, - 4133292154170828382, 2918308698224194548, 1519461397937144458, 5293934712616591764, - 4922828954023452664, 2879211533496425641, 5896236396443472108, 8465043815351752425, - 7329020396871624740, 8915471717014488588, 2944902635677463047, 7052079073493465134, + 6346751753565857109, -8982212049534145501, -6127578587196093755, -245039190118465649, + -6320577374581628592, 7208698530190629697, 7276901792339343736, -7490986807540332668, + 4133292154170828382, 2918308698224194548, -7703910638917631350, -3929437324238184044, + -4300543082831323144, -6344160503358350167, 5896236396443472108, -758328221503023383, + -1894351639983151068, -307900319840287220, -6278469401177312761, -2171292963361310674, 8382142935188824023, 9103922860780351547, 4152330101494654406, } ) @@ -223,13 +221,18 @@ func (rng *rngSource) Seed(seed int64) { x = seedrand(x) u ^= int64(x) u ^= rng_cooked[i] - rng.vec[i] = u & _MASK + rng.vec[i] = u } } } // Int63 returns a non-negative pseudo-random 63-bit integer as an int64. func (rng *rngSource) Int63() int64 { + return int64(rng.Uint64() & _MASK) +} + +// Uint64 returns a non-negative pseudo-random 64-bit integer as an uint64. +func (rng *rngSource) Uint64() uint64 { rng.tap-- if rng.tap < 0 { rng.tap += _LEN @@ -240,7 +243,7 @@ func (rng *rngSource) Int63() int64 { rng.feed += _LEN } - x := (rng.vec[rng.feed] + rng.vec[rng.tap]) & _MASK + x := rng.vec[rng.feed] + rng.vec[rng.tap] rng.vec[rng.feed] = x - return x + return uint64(x) } diff --git a/libgo/go/math/sin.go b/libgo/go/math/sin.go index 1c5491f..75579ab 100644 --- a/libgo/go/math/sin.go +++ b/libgo/go/math/sin.go @@ -146,8 +146,8 @@ func cos(x float64) float64 { // map zeros to origin if j&1 == 1 { - j += 1 - y += 1 + j++ + y++ } j &= 7 // octant modulo 2Pi radians (360 degrees) if j > 3 { @@ -212,8 +212,8 @@ func sin(x float64) float64 { // map zeros to origin if j&1 == 1 { - j += 1 - y += 1 + j++ + y++ } j &= 7 // octant modulo 2Pi radians (360 degrees) // reflect in x axis diff --git a/libgo/go/math/sincos.go b/libgo/go/math/sincos.go index b3a2f8a..89db81e 100644 --- a/libgo/go/math/sincos.go +++ b/libgo/go/math/sincos.go @@ -42,8 +42,8 @@ func sincos(x float64) (sin, cos float64) { y := float64(j) // integer part of x/(Pi/4), as float if j&1 == 1 { // map zeros to origin - j += 1 - y += 1 + j++ + y++ } j &= 7 // octant modulo 2Pi radians (360 degrees) if j > 3 { // reflect in x axis diff --git a/libgo/go/math/tan.go b/libgo/go/math/tan.go index e544b27..f5230d3 100644 --- a/libgo/go/math/tan.go +++ b/libgo/go/math/tan.go @@ -114,8 +114,8 @@ func tan(x float64) float64 { /* map zeros and singularities to origin */ if j&1 == 1 { - j += 1 - y += 1 + j++ + y++ } z := ((x - y*PI4A) - y*PI4B) - y*PI4C |