cmd/compile/internal/big: update vendored math/big
This updates the big package used by the compiler to match the
public big package which contains some updates and bug fixes.
Obtained by running vendor.bash in the internal/big directory.
No manual changes.
Change-Id: I299aecc6599d4a745a721ce48def32449640dbb2
Reviewed-on: https://go-review.googlesource.com/13815
Reviewed-by: Ian Lance Taylor <iant@golang.org>
diff --git a/src/cmd/compile/internal/big/example_test.go b/src/cmd/compile/internal/big/example_test.go
index cb91bc2..8a71a08 100644
--- a/src/cmd/compile/internal/big/example_test.go
+++ b/src/cmd/compile/internal/big/example_test.go
@@ -8,6 +8,7 @@
"cmd/compile/internal/big"
"fmt"
"log"
+ "math"
)
func ExampleRat_SetString() {
@@ -49,3 +50,79 @@
}
// Output: 18446744073709551617
}
+
+// This example demonstrates how to use big.Int to compute the smallest
+// Fibonacci number with 100 decimal digits and to test whether it is prime.
+func Example_fibonacci() {
+ // Initialize two big ints with the first two numbers in the sequence.
+ a := big.NewInt(0)
+ b := big.NewInt(1)
+
+ // Initialize limit as 10^99, the smallest integer with 100 digits.
+ var limit big.Int
+ limit.Exp(big.NewInt(10), big.NewInt(99), nil)
+
+ // Loop while a is smaller than 1e100.
+ for a.Cmp(&limit) < 0 {
+ // Compute the next Fibonacci number, storing it in a.
+ a.Add(a, b)
+ // Swap a and b so that b is the next number in the sequence.
+ a, b = b, a
+ }
+ fmt.Println(a) // 100-digit Fibonacci number
+
+ // Test a for primality.
+ // (ProbablyPrimes' argument sets the number of Miller-Rabin
+ // rounds to be performed. 20 is a good value.)
+ fmt.Println(a.ProbablyPrime(20))
+
+ // Output:
+ // 1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757
+ // false
+}
+
+// This example shows how to use big.Float to compute the square root of 2 with
+// a precision of 200 bits, and how to print the result as a decimal number.
+func Example_sqrt2() {
+ // We'll do computations with 200 bits of precision in the mantissa.
+ const prec = 200
+
+ // Compute the square root of 2 using Newton's Method. We start with
+ // an initial estimate for sqrt(2), and then iterate:
+ // x_{n+1} = 1/2 * ( x_n + (2.0 / x_n) )
+
+ // Since Newton's Method doubles the number of correct digits at each
+ // iteration, we need at least log_2(prec) steps.
+ steps := int(math.Log2(prec))
+
+ // Initialize values we need for the computation.
+ two := new(big.Float).SetPrec(prec).SetInt64(2)
+ half := new(big.Float).SetPrec(prec).SetFloat64(0.5)
+
+ // Use 1 as the initial estimate.
+ x := new(big.Float).SetPrec(prec).SetInt64(1)
+
+ // We use t as a temporary variable. There's no need to set its precision
+ // since big.Float values with unset (== 0) precision automatically assume
+ // the largest precision of the arguments when used as the result (receiver)
+ // of a big.Float operation.
+ t := new(big.Float)
+
+ // Iterate.
+ for i := 0; i <= steps; i++ {
+ t.Quo(two, x) // t = 2.0 / x_n
+ t.Add(x, t) // t = x_n + (2.0 / x_n)
+ x.Mul(half, t) // x_{n+1} = 0.5 * t
+ }
+
+ // We can use the usual fmt.Printf verbs since big.Float implements fmt.Formatter
+ fmt.Printf("sqrt(2) = %.50f\n", x)
+
+ // Print the error between 2 and x*x.
+ t.Mul(x, x) // t = x*x
+ fmt.Printf("error = %e\n", t.Sub(two, t))
+
+ // Output:
+ // sqrt(2) = 1.41421356237309504880168872420969807856967187537695
+ // error = 0.000000e+00
+}
diff --git a/src/cmd/compile/internal/big/floatconv.go b/src/cmd/compile/internal/big/floatconv.go
index 4a070ca..0e8b7b6 100644
--- a/src/cmd/compile/internal/big/floatconv.go
+++ b/src/cmd/compile/internal/big/floatconv.go
@@ -125,9 +125,9 @@
// apply 10**exp10
p := new(Float).SetPrec(z.Prec() + 64) // use more bits for p -- TODO(gri) what is the right number?
if exp10 < 0 {
- z.uquo(z, p.pow10(-exp10))
+ z.Quo(z, p.pow10(-exp10))
} else {
- z.umul(z, p.pow10(exp10))
+ z.Mul(z, p.pow10(exp10))
}
return
diff --git a/src/cmd/compile/internal/big/floatconv_test.go b/src/cmd/compile/internal/big/floatconv_test.go
index 4f23953..156e1af 100644
--- a/src/cmd/compile/internal/big/floatconv_test.go
+++ b/src/cmd/compile/internal/big/floatconv_test.go
@@ -367,9 +367,9 @@
// make sure "stupid" exponents don't stall the machine
{"1e1000000", 64, 'p', 0, "0x.88b3a28a05eade3ap+3321929"},
- {"1e1000000000", 64, 'p', 0, "0x.ecc5f45aa573d3p+1538481529"},
+ {"1e1000000000", 64, 'p', 0, "+Inf"},
{"1e-1000000", 64, 'p', 0, "0x.efb4542cc8ca418ap-3321928"},
- {"1e-1000000000", 64, 'p', 0, "0x.8a64dd983a4c7dabp-1538481528"},
+ {"1e-1000000000", 64, 'p', 0, "0"},
// TODO(gri) need tests for actual large Floats
diff --git a/src/cmd/compile/internal/big/int.go b/src/cmd/compile/internal/big/int.go
index 5e31253..65334e0 100644
--- a/src/cmd/compile/internal/big/int.go
+++ b/src/cmd/compile/internal/big/int.go
@@ -500,15 +500,17 @@
// use one Euclidean iteration to ensure that u and v are approx. the same size
switch {
case len(a.abs) > len(b.abs):
- u.Set(b)
+ // must set v before u since u may be alias for a or b (was issue #11284)
v.Rem(a, b)
+ u.Set(b)
case len(a.abs) < len(b.abs):
- u.Set(a)
v.Rem(b, a)
- default:
u.Set(a)
+ default:
v.Set(b)
+ u.Set(a)
}
+ // a, b must not be used anymore (may be aliases with u)
// v might be 0 now
if len(v.abs) == 0 {
diff --git a/src/cmd/compile/internal/big/int_test.go b/src/cmd/compile/internal/big/int_test.go
index 16eed9a..9787462 100644
--- a/src/cmd/compile/internal/big/int_test.go
+++ b/src/cmd/compile/internal/big/int_test.go
@@ -387,6 +387,11 @@
}
func checkBytes(b []byte) bool {
+ // trim leading zero bytes since Bytes() won't return them
+ // (was issue 12231)
+ for len(b) > 0 && b[0] == 0 {
+ b = b[1:]
+ }
b2 := new(Int).SetBytes(b).Bytes()
return bytes.Equal(b, b2)
}
@@ -662,6 +667,21 @@
if D.Cmp(d) != 0 {
t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, D, d)
}
+
+ // check results in presence of aliasing (issue #11284)
+ a2 := new(Int).Set(a)
+ b2 := new(Int).Set(b)
+ a2.binaryGCD(a2, b2) // result is same as 1st argument
+ if a2.Cmp(d) != 0 {
+ t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, a2, d)
+ }
+
+ a2 = new(Int).Set(a)
+ b2 = new(Int).Set(b)
+ b2.binaryGCD(a2, b2) // result is same as 2nd argument
+ if b2.Cmp(d) != 0 {
+ t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, b2, d)
+ }
}
func TestGcd(t *testing.T) {
diff --git a/src/cmd/compile/internal/big/intconv.go b/src/cmd/compile/internal/big/intconv.go
index 9c68a22..737d176 100644
--- a/src/cmd/compile/internal/big/intconv.go
+++ b/src/cmd/compile/internal/big/intconv.go
@@ -101,31 +101,31 @@
digits := x.abs.string(cs)
// number of characters for the three classes of number padding
- var left int // space characters to left of digits for right justification ("%8d")
- var zeroes int // zero characters (actually cs[0]) as left-most digits ("%.8d")
- var right int // space characters to right of digits for left justification ("%-8d")
+ var left int // space characters to left of digits for right justification ("%8d")
+ var zeros int // zero characters (actually cs[0]) as left-most digits ("%.8d")
+ var right int // space characters to right of digits for left justification ("%-8d")
// determine number padding from precision: the least number of digits to output
precision, precisionSet := s.Precision()
if precisionSet {
switch {
case len(digits) < precision:
- zeroes = precision - len(digits) // count of zero padding
+ zeros = precision - len(digits) // count of zero padding
case digits == "0" && precision == 0:
return // print nothing if zero value (x == 0) and zero precision ("." or ".0")
}
}
// determine field pad from width: the least number of characters to output
- length := len(sign) + len(prefix) + zeroes + len(digits)
+ length := len(sign) + len(prefix) + zeros + len(digits)
if width, widthSet := s.Width(); widthSet && length < width { // pad as specified
switch d := width - length; {
case s.Flag('-'):
// pad on the right with spaces; supersedes '0' when both specified
right = d
case s.Flag('0') && !precisionSet:
- // pad with zeroes unless precision also specified
- zeroes = d
+ // pad with zeros unless precision also specified
+ zeros = d
default:
// pad on the left with spaces
left = d
@@ -136,7 +136,7 @@
writeMultiple(s, " ", left)
writeMultiple(s, sign, 1)
writeMultiple(s, prefix, 1)
- writeMultiple(s, "0", zeroes)
+ writeMultiple(s, "0", zeros)
writeMultiple(s, digits, 1)
writeMultiple(s, " ", right)
}
diff --git a/src/cmd/compile/internal/big/natconv.go b/src/cmd/compile/internal/big/natconv.go
index 022dcfe..80da307 100644
--- a/src/cmd/compile/internal/big/natconv.go
+++ b/src/cmd/compile/internal/big/natconv.go
@@ -252,14 +252,15 @@
// by len(charset), which must be >= 2 and <= 256.
func (x nat) string(charset string) string {
b := Word(len(charset))
-
- // special cases
- switch {
- case b < 2 || b > 256:
+ if b < 2 || b > 256 {
panic("invalid character set length")
- case len(x) == 0:
+ }
+
+ // x == 0
+ if len(x) == 0 {
return string(charset[0])
}
+ // len(x) > 0
// allocate buffer for conversion
i := int(float64(x.bitLen())/math.Log2(float64(b))) + 1 // off by one at most
@@ -267,13 +268,13 @@
// convert power of two and non power of two bases separately
if b == b&-b {
- // shift is base-b digit size in bits
+ // shift is base b digit size in bits
shift := trailingZeroBits(b) // shift > 0 because b >= 2
- mask := Word(1)<<shift - 1
- w := x[0]
+ mask := Word(1<<shift - 1)
+ w := x[0] // current word
nbits := uint(_W) // number of unprocessed bits in w
- // convert less-significant words
+ // convert less-significant words (include leading zeros)
for k := 1; k < len(x); k++ {
// convert full digits
for nbits >= shift {
@@ -289,7 +290,7 @@
w = x[k]
nbits = _W
} else {
- // partial digit in current (k-1) and next (k) word
+ // partial digit in current word w (== x[k-1]) and next word x[k]
w |= x[k] << nbits
i--
s[i] = charset[w&mask]
@@ -300,12 +301,11 @@
}
}
- // convert digits of most-significant word (omit leading zeros)
- for nbits >= 0 && w != 0 {
+ // convert digits of most-significant word w (omit leading zeros)
+ for w != 0 {
i--
s[i] = charset[w&mask]
w >>= shift
- nbits -= shift
}
} else {
@@ -409,9 +409,9 @@
}
}
- // prepend high-order zeroes
+ // prepend high-order zeros
zero := charset[0]
- for i > 0 { // while need more leading zeroes
+ for i > 0 { // while need more leading zeros
i--
s[i] = zero
}
@@ -425,7 +425,7 @@
type divisor struct {
bbb nat // divisor
- nbits int // bit length of divisor (discounting leading zeroes) ~= log2(bbb)
+ nbits int // bit length of divisor (discounting leading zeros) ~= log2(bbb)
ndigits int // digit length of divisor in terms of output base digits
}
diff --git a/src/cmd/compile/internal/big/ratconv.go b/src/cmd/compile/internal/big/ratconv.go
index 778077b..961ff64 100644
--- a/src/cmd/compile/internal/big/ratconv.go
+++ b/src/cmd/compile/internal/big/ratconv.go
@@ -205,7 +205,8 @@
}
// FloatString returns a string representation of x in decimal form with prec
-// digits of precision after the decimal point and the last digit rounded.
+// digits of precision after the decimal point. The last digit is rounded to
+// nearest, with halves rounded away from zero.
func (x *Rat) FloatString(prec int) string {
if x.IsInt() {
s := x.a.String()
diff --git a/src/cmd/compile/internal/big/ratconv_test.go b/src/cmd/compile/internal/big/ratconv_test.go
index 16b3a19..da2fdab 100644
--- a/src/cmd/compile/internal/big/ratconv_test.go
+++ b/src/cmd/compile/internal/big/ratconv_test.go
@@ -113,6 +113,8 @@
{"1", 0, "1"},
{"1", 2, "1.00"},
{"-1", 0, "-1"},
+ {"0.05", 1, "0.1"},
+ {"-0.05", 1, "-0.1"},
{".25", 2, "0.25"},
{".25", 1, "0.3"},
{".25", 3, "0.250"},
