diff options
Diffstat (limited to 'libgo/go/math/big')
25 files changed, 1023 insertions, 251 deletions
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 00000000000..0f11481f6d2 --- /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 00000000000..ee127a4fc92 --- /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 75862b4951f..f2b30830009 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 2c0c9daebc1..2dfa032c776 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 15bdb181e72..424811e15af 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 a3c23751ba4..65ed019b741 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 7a9c2b3dfb2..aabd7b44777 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 464619b3380..7d4bd312c9b 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 a884df6fe1c..95d1bf84e24 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 b2a1ab05fcc..edcb2eb1050 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 05bce613a80..8645c44f103 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 3725d4b8345..d1c1dab0691 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 57b16e1ad1f..d2a85886c72 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 a929bf597f4..3cca2ecd0c8 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 f2a75d1cd50..1d8dabce12b 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 45a3765d3ee..b8e0778ca32 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 daf674aef4e..91a62ce04e1 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 4ff57b6464e..ee1e4143ed9 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 2e65d2a7ef7..9b1a626c4cf 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 79901d18804..bdb60e68e0a 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 00000000000..3e9690e55e6 --- /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 00000000000..a2d3d18f8f4 --- /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 3a06fca3c34..afda68658f7 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 ef2b6750d0c..a6a401c8576 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 35ad6ccea77..56ac8d7aa3a 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:"):] |