From 5a8ea165926cb0737ab03bc48c18dc5198ab5305 Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Thu, 2 Jan 2020 15:05:27 -0800 Subject: libgo: update to Go1.14beta1 Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/214297 --- libgo/go/math/big/floatconv_test.go | 4 + libgo/go/math/big/ftoa.go | 3 +- libgo/go/math/big/int.go | 50 ++++++--- libgo/go/math/big/int_test.go | 33 ++++-- libgo/go/math/big/nat.go | 210 +++++++++++++++++++++++++++++++++--- libgo/go/math/big/nat_test.go | 76 ++++++++++++- libgo/go/math/big/rat.go | 70 ++++++------ libgo/go/math/big/rat_test.go | 56 +++++++++- libgo/go/math/big/ratconv.go | 2 +- 9 files changed, 434 insertions(+), 70 deletions(-) (limited to 'libgo/go/math/big') diff --git a/libgo/go/math/big/floatconv_test.go b/libgo/go/math/big/floatconv_test.go index c6c6ba6..3aa6834 100644 --- a/libgo/go/math/big/floatconv_test.go +++ b/libgo/go/math/big/floatconv_test.go @@ -536,6 +536,10 @@ func TestFloatText(t *testing.T) { {"-8191.53125", ToNegativeInf, 53, 'x', 4, "-0x1.fff9p+12"}, {"8191.53125", ToPositiveInf, 53, 'x', 4, "0x1.fff9p+12"}, {"-8191.53125", ToPositiveInf, 53, 'x', 4, "-0x1.fff8p+12"}, + + // issue 34343 + {"0x.8p-2147483648", ToNearestEven, 4, 'p', -1, "0x.8p-2147483648"}, + {"0x.8p-2147483648", ToNearestEven, 4, 'x', -1, "0x1p-2147483649"}, } { f, _, err := ParseFloat(test.x, 0, test.prec, ToNearestEven) if err != nil { diff --git a/libgo/go/math/big/ftoa.go b/libgo/go/math/big/ftoa.go index 6cae63e..5506e6e 100644 --- a/libgo/go/math/big/ftoa.go +++ b/libgo/go/math/big/ftoa.go @@ -384,7 +384,7 @@ func (x *Float) fmtX(buf []byte, prec int) []byte { case w > n: m = nat(nil).shr(m, w-n) } - exp := x.exp - 1 + exp64 := int64(x.exp) - 1 // avoid wrap-around hm := m.utoa(16) if debugFloat && hm[0] != '1' { @@ -397,7 +397,6 @@ func (x *Float) fmtX(buf []byte, prec int) []byte { } buf = append(buf, 'p') - exp64 := int64(exp) if exp64 >= 0 { buf = append(buf, '+') } else { diff --git a/libgo/go/math/big/int.go b/libgo/go/math/big/int.go index 8e52f0a..bf1fa73 100644 --- a/libgo/go/math/big/int.go +++ b/libgo/go/math/big/int.go @@ -323,6 +323,8 @@ func (x *Int) Cmp(y *Int) (r int) { // (-x) cmp y == y // (-x) cmp (-y) == -(x cmp y) switch { + case x == y: + // nothing to do case x.neg == y.neg: r = x.abs.cmp(y.abs) if x.neg { @@ -466,7 +468,7 @@ func (x *Int) TrailingZeroBits() uint { // If m == nil or m == 0, z = x**y unless y <= 0 then z = 1. If m > 0, y < 0, // and x and n are not relatively prime, z is unchanged and nil is returned. // -// Modular exponentation of inputs of a particular size is not a +// Modular exponentiation 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. @@ -500,18 +502,36 @@ func (z *Int) Exp(x, y, m *Int) *Int { return z } -// GCD sets z to the greatest common divisor of a and b, which both must -// be > 0, and returns z. +// GCD sets z to the greatest common divisor of a and b and returns z. // If x or y are not nil, GCD sets their value such that z = a*x + b*y. -// If either a or b is <= 0, GCD sets z = x = y = 0. +// Regardless of the signs of a and b, z is always >= 0. +// If a == b == 0, GCD sets z = x = y = 0. +// If a == 0 and b != 0, GCD sets z = |b|, x = 0, y = sign(b) * 1. +// If a != 0 and b == 0, GCD sets z = |a|, x = sign(a) * 1, y = 0. func (z *Int) GCD(x, y, a, b *Int) *Int { - if a.Sign() <= 0 || b.Sign() <= 0 { - z.SetInt64(0) + if len(a.abs) == 0 || len(b.abs) == 0 { + lenA, lenB, negA, negB := len(a.abs), len(b.abs), a.neg, b.neg + if lenA == 0 { + z.Set(b) + } else { + z.Set(a) + } + z.neg = false if x != nil { - x.SetInt64(0) + if lenA == 0 { + x.SetUint64(0) + } else { + x.SetUint64(1) + x.neg = negA + } } if y != nil { - y.SetInt64(0) + if lenB == 0 { + y.SetUint64(0) + } else { + y.SetUint64(1) + y.neg = negB + } } return z } @@ -619,7 +639,7 @@ func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool) { } // lehmerGCD sets z to the greatest common divisor of a and b, -// which both must be > 0, and returns z. +// which both must be != 0, and returns z. // If x or y are not nil, their values are set such that z = a*x + b*y. // See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm L. // This implementation uses the improved condition by Collins requiring only one @@ -631,8 +651,8 @@ func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool) { func (z *Int) lehmerGCD(x, y, a, b *Int) *Int { var A, B, Ua, Ub *Int - A = new(Int).Set(a) - B = new(Int).Set(b) + A = new(Int).Abs(a) + B = new(Int).Abs(b) extended := x != nil || y != nil @@ -718,7 +738,7 @@ func (z *Int) lehmerGCD(x, y, a, b *Int) *Int { A.abs[0] = aWord } } - + negA := a.neg if y != nil { // avoid aliasing b needed in the division below if y == b { @@ -728,12 +748,18 @@ func (z *Int) lehmerGCD(x, y, a, b *Int) *Int { } // y = (z - a*x)/b y.Mul(a, Ua) // y can safely alias a + if negA { + y.neg = !y.neg + } y.Sub(A, y) y.Div(y, B) } if x != nil { *x = *Ua + if negA { + x.neg = !x.neg + } } *z = *A diff --git a/libgo/go/math/big/int_test.go b/libgo/go/math/big/int_test.go index ade973b..e3a1587 100644 --- a/libgo/go/math/big/int_test.go +++ b/libgo/go/math/big/int_test.go @@ -757,11 +757,13 @@ var gcdTests = []struct { }{ // a <= 0 || b <= 0 {"0", "0", "0", "0", "0"}, - {"0", "0", "0", "0", "7"}, - {"0", "0", "0", "11", "0"}, - {"0", "0", "0", "-77", "35"}, - {"0", "0", "0", "64515", "-24310"}, - {"0", "0", "0", "-64515", "-24310"}, + {"7", "0", "1", "0", "7"}, + {"7", "0", "-1", "0", "-7"}, + {"11", "1", "0", "11", "0"}, + {"7", "-1", "-2", "-77", "35"}, + {"935", "-3", "8", "64515", "24310"}, + {"935", "-3", "-8", "64515", "-24310"}, + {"935", "3", "-8", "-64515", "-24310"}, {"1", "-9", "47", "120", "23"}, {"7", "1", "-2", "77", "35"}, @@ -1071,6 +1073,20 @@ func TestCmpAbs(t *testing.T) { } } +func TestIntCmpSelf(t *testing.T) { + for _, s := range cmpAbsTests { + x, ok := new(Int).SetString(s, 0) + if !ok { + t.Fatalf("SetString(%s, 0) failed", s) + } + got := x.Cmp(x) + want := 0 + if got != want { + t.Errorf("x = %s: x.Cmp(x): got %d; want %d", x, got, want) + } + } +} + var int64Tests = []string{ // int64 "0", @@ -1813,8 +1829,11 @@ func benchmarkDiv(b *testing.B, aSize, bSize int) { } func BenchmarkDiv(b *testing.B) { - min, max, step := 10, 100000, 10 - for i := min; i <= max; i *= step { + sizes := []int{ + 10, 20, 50, 100, 200, 500, 1000, + 1e4, 1e5, 1e6, 1e7, + } + for _, i := range sizes { j := 2 * i b.Run(fmt.Sprintf("%d/%d", j, i), func(b *testing.B) { benchmarkDiv(b, j, i) diff --git a/libgo/go/math/big/nat.go b/libgo/go/math/big/nat.go index 22d7a6c..1b771ca 100644 --- a/libgo/go/math/big/nat.go +++ b/libgo/go/math/big/nat.go @@ -463,7 +463,8 @@ func (z nat) mul(x, y nat) nat { // be a larger valid threshold contradicting the assumption about k. // if k < n || m != n { - var t nat + tp := getNat(3 * k) + t := *tp // add x0*y1*b x0 := x0.norm() @@ -484,6 +485,8 @@ func (z nat) mul(x, y nat) nat { t = t.mul(xi, y1) addAt(z, t, i+k) } + + putNat(tp) } return z.norm() @@ -495,7 +498,9 @@ func (z nat) mul(x, y nat) nat { // The (non-normalized) result is placed in z. func basicSqr(z, x nat) { n := len(x) - t := make(nat, 2*n) // temporary variable to hold the products + tp := getNat(2 * n) + t := *tp // temporary variable to hold the products + t.clear() z[1], z[0] = mulWW(x[0], x[0]) // the initial square for i := 1; i < n; i++ { d := x[i] @@ -506,6 +511,7 @@ func basicSqr(z, x nat) { } t[2*n-1] = shlVU(t[1:2*n-1], t[1:2*n-1], 1) // double the j < i products addVV(z, z, t) // combine the result + putNat(tp) } // karatsubaSqr squares x and leaves the result in z. @@ -592,7 +598,8 @@ func (z nat) sqr(x nat) nat { z[2*k:].clear() if k < n { - var t nat + tp := getNat(2 * k) + t := *tp x0 := x0.norm() x1 := x[k:] t = t.mul(x0, x1) @@ -600,6 +607,7 @@ func (z nat) sqr(x nat) nat { addAt(z, t, k) // z = 2*x1*x0*b + x0^2 t = t.sqr(x1) addAt(z, t, 2*k) // z = x1^2*b^2 + 2*x1*x0*b + x0^2 + putNat(tp) } return z.norm() @@ -685,7 +693,7 @@ func putNat(x *nat) { var natPool sync.Pool -// q = (uIn-r)/vIn, with 0 <= r < y +// q = (uIn-r)/vIn, with 0 <= r < vIn // Uses z as storage for q, and u as storage for r if possible. // See Knuth, Volume 2, section 4.3.1, Algorithm D. // Preconditions: @@ -713,6 +721,30 @@ func (z nat) divLarge(u, uIn, vIn nat) (q, r nat) { } q = z.make(m + 1) + if n < divRecursiveThreshold { + q.divBasic(u, v) + } else { + q.divRecursive(u, v) + } + putNat(vp) + + q = q.norm() + shrVU(u, u, shift) + r = u.norm() + + return q, r +} + +// divBasic performs word-by-word division of u by v. +// The quotient is written in pre-allocated q. +// The remainder overwrites input u. +// +// Precondition: +// - len(q) >= len(u)-len(v) +func (q nat) divBasic(u, v nat) { + n := len(v) + m := len(u) - n + qhatvp := getNat(n + 1) qhatv := *qhatvp @@ -721,7 +753,11 @@ func (z nat) divLarge(u, uIn, vIn nat) (q, r nat) { for j := m; j >= 0; j-- { // D3. qhat := Word(_M) - if ujn := u[j+n]; ujn != vn1 { + var ujn Word + if j+n < len(u) { + ujn = u[j+n] + } + if ujn != vn1 { var rhat Word qhat, rhat = divWW(ujn, u[j+n-1], vn1) @@ -744,25 +780,175 @@ func (z nat) divLarge(u, uIn, vIn nat) (q, r nat) { // D4. qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0) - - c := subVV(u[j:j+len(qhatv)], u[j:], qhatv) + qhl := len(qhatv) + if j+qhl > len(u) && qhatv[n] == 0 { + qhl-- + } + c := subVV(u[j:j+qhl], u[j:], qhatv) if c != 0 { c := addVV(u[j:j+n], u[j:], v) u[j+n] += c qhat-- } + if j == m && m == len(q) && qhat == 0 { + continue + } q[j] = qhat } - putNat(vp) putNat(qhatvp) +} - q = q.norm() - shrVU(u, u, shift) - r = u.norm() +const divRecursiveThreshold = 100 - return q, r +// divRecursive performs word-by-word division of u by v. +// The quotient is written in pre-allocated z. +// The remainder overwrites input u. +// +// Precondition: +// - len(z) >= len(u)-len(v) +// +// See Burnikel, Ziegler, "Fast Recursive Division", Algorithm 1 and 2. +func (z nat) divRecursive(u, v nat) { + // Recursion depth is less than 2 log2(len(v)) + // Allocate a slice of temporaries to be reused across recursion. + recDepth := 2 * bits.Len(uint(len(v))) + // large enough to perform Karatsuba on operands as large as v + tmp := getNat(3 * len(v)) + temps := make([]*nat, recDepth) + z.clear() + z.divRecursiveStep(u, v, 0, tmp, temps) + for _, n := range temps { + if n != nil { + putNat(n) + } + } + putNat(tmp) +} + +func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat) { + u = u.norm() + v = v.norm() + + if len(u) == 0 { + z.clear() + return + } + n := len(v) + if n < divRecursiveThreshold { + z.divBasic(u, v) + return + } + m := len(u) - n + if m < 0 { + return + } + + // Produce the quotient by blocks of B words. + // Division by v (length n) is done using a length n/2 division + // and a length n/2 multiplication for each block. The final + // complexity is driven by multiplication complexity. + B := n / 2 + + // Allocate a nat for qhat below. + if temps[depth] == nil { + temps[depth] = getNat(n) + } else { + *temps[depth] = temps[depth].make(B + 1) + } + + j := m + for j > B { + // Divide u[j-B:j+n] by vIn. Keep remainder in u + // for next block. + // + // The following property will be used (Lemma 2): + // if u = u1 << s + u0 + // v = v1 << s + v0 + // then floor(u1/v1) >= floor(u/v) + // + // Moreover, the difference is at most 2 if len(v1) >= len(u/v) + // We choose s = B-1 since len(v)-B >= B+1 >= len(u/v) + s := (B - 1) + // Except for the first step, the top bits are always + // a division remainder, so the quotient length is <= n. + uu := u[j-B:] + + qhat := *temps[depth] + qhat.clear() + qhat.divRecursiveStep(uu[s:B+n], v[s:], depth+1, tmp, temps) + qhat = qhat.norm() + // Adjust the quotient: + // u = u_h << s + u_l + // v = v_h << s + v_l + // u_h = q̂ v_h + rh + // u = q̂ (v - v_l) + rh << s + u_l + // After the above step, u contains a remainder: + // u = rh << s + u_l + // and we need to subtract q̂ v_l + // + // But it may be a bit too large, in which case q̂ needs to be smaller. + qhatv := tmp.make(3 * n) + qhatv.clear() + qhatv = qhatv.mul(qhat, v[:s]) + for i := 0; i < 2; i++ { + e := qhatv.cmp(uu.norm()) + if e <= 0 { + break + } + subVW(qhat, qhat, 1) + c := subVV(qhatv[:s], qhatv[:s], v[:s]) + if len(qhatv) > s { + subVW(qhatv[s:], qhatv[s:], c) + } + addAt(uu[s:], v[s:], 0) + } + if qhatv.cmp(uu.norm()) > 0 { + panic("impossible") + } + c := subVV(uu[:len(qhatv)], uu[:len(qhatv)], qhatv) + if c > 0 { + subVW(uu[len(qhatv):], uu[len(qhatv):], c) + } + addAt(z, qhat, j-B) + j -= B + } + + // Now u < (v< 0 { + subVW(qhat, qhat, 1) + c := subVV(qhatv[:s], qhatv[:s], v[:s]) + if len(qhatv) > s { + subVW(qhatv[s:], qhatv[s:], c) + } + addAt(u[s:], v[s:], 0) + } + } + if qhatv.cmp(u.norm()) > 0 { + panic("impossible") + } + c := subVV(u[0:len(qhatv)], u[0:len(qhatv)], qhatv) + if c > 0 { + c = subVW(u[len(qhatv):], u[len(qhatv):], c) + } + if c > 0 { + panic("impossible") + } + + // Done! + addAt(z, qhat.norm(), 0) } // Length of x in bits. x must be normalized. diff --git a/libgo/go/math/big/nat_test.go b/libgo/go/math/big/nat_test.go index 3c79495..32f29e3 100644 --- a/libgo/go/math/big/nat_test.go +++ b/libgo/go/math/big/nat_test.go @@ -192,10 +192,22 @@ func TestMulUnbalanced(t *testing.T) { } } +// rndNat returns a random nat value >= 0 of (usually) n words in length. +// In extremely unlikely cases it may be smaller than n words if the top- +// most words are 0. func rndNat(n int) nat { return nat(rndV(n)).norm() } +// rndNat1 is like rndNat but the result is guaranteed to be > 0. +func rndNat1(n int) nat { + x := nat(rndV(n)).norm() + if len(x) == 0 { + x.setWord(1) + } + return x +} + func BenchmarkMul(b *testing.B) { mulx := rndNat(1e4) muly := rndNat(1e4) @@ -206,6 +218,29 @@ func BenchmarkMul(b *testing.B) { } } +func benchmarkNatMul(b *testing.B, nwords int) { + x := rndNat(nwords) + y := rndNat(nwords) + var z nat + b.ResetTimer() + for i := 0; i < b.N; i++ { + z.mul(x, y) + } +} + +var mulBenchSizes = []int{10, 100, 1000, 10000, 100000} + +func BenchmarkNatMul(b *testing.B) { + for _, n := range mulBenchSizes { + if isRaceBuilder && n > 1e3 { + continue + } + b.Run(fmt.Sprintf("%d", n), func(b *testing.B) { + benchmarkNatMul(b, n) + }) + } +} + func TestNLZ(t *testing.T) { var x Word = _B >> 1 for i := 0; i <= _W; i++ { @@ -681,7 +716,11 @@ func benchmarkNatSqr(b *testing.B, nwords int) { } } -var sqrBenchSizes = []int{1, 2, 3, 5, 8, 10, 20, 30, 50, 80, 100, 200, 300, 500, 800, 1000} +var sqrBenchSizes = []int{ + 1, 2, 3, 5, 8, 10, 20, 30, 50, 80, + 100, 200, 300, 500, 800, + 1000, 10000, 100000, +} func BenchmarkNatSqr(b *testing.B) { for _, n := range sqrBenchSizes { @@ -712,3 +751,38 @@ func BenchmarkNatSetBytes(b *testing.B) { }) } } + +func TestNatDiv(t *testing.T) { + sizes := []int{ + 1, 2, 5, 8, 15, 25, 40, 65, 100, + 200, 500, 800, 1500, 2500, 4000, 6500, 10000, + } + for _, i := range sizes { + for _, j := range sizes { + a := rndNat1(i) + b := rndNat1(j) + // the test requires b >= 2 + if len(b) == 1 && b[0] == 1 { + b[0] = 2 + } + // choose a remainder c < b + c := rndNat1(len(b)) + if len(c) == len(b) && c[len(c)-1] >= b[len(b)-1] { + c[len(c)-1] = 0 + c = c.norm() + } + // compute x = a*b+c + x := nat(nil).mul(a, b) + x = x.add(x, c) + + var q, r nat + q, r = q.div(r, x, b) + if q.cmp(a) != 0 { + t.Fatalf("wrong quotient: got %s; want %s for %s/%s", q.utoa(10), a.utoa(10), x.utoa(10), b.utoa(10)) + } + if r.cmp(c) != 0 { + t.Fatalf("wrong remainder: got %s; want %s for %s/%s", r.utoa(10), c.utoa(10), x.utoa(10), b.utoa(10)) + } + } + } +} diff --git a/libgo/go/math/big/rat.go b/libgo/go/math/big/rat.go index c8bf698..d35cd4c 100644 --- a/libgo/go/math/big/rat.go +++ b/libgo/go/math/big/rat.go @@ -22,7 +22,9 @@ import ( // of Rats are not supported and may lead to errors. type Rat struct { // To make zero values for Rat work w/o initialization, - // a zero value of b (len(b) == 0) acts like b == 1. + // a zero value of b (len(b) == 0) acts like b == 1. At + // the earliest opportunity (when an assignment to the Rat + // is made), such uninitialized denominators are set to 1. // a.neg determines the sign of the Rat, b.neg is ignored. a, b Int } @@ -271,7 +273,7 @@ func quotToFloat64(a, b nat) (f float64, exact bool) { func (x *Rat) Float32() (f float32, exact bool) { b := x.b.abs if len(b) == 0 { - b = b.set(natOne) // materialize denominator + b = natOne } f, exact = quotToFloat32(x.a.abs, b) if x.a.neg { @@ -287,7 +289,7 @@ func (x *Rat) Float32() (f float32, exact bool) { func (x *Rat) Float64() (f float64, exact bool) { b := x.b.abs if len(b) == 0 { - b = b.set(natOne) // materialize denominator + b = natOne } f, exact = quotToFloat64(x.a.abs, b) if x.a.neg { @@ -297,6 +299,7 @@ func (x *Rat) Float64() (f float64, exact bool) { } // SetFrac sets z to a/b and returns z. +// If b == 0, SetFrac panics. func (z *Rat) SetFrac(a, b *Int) *Rat { z.a.neg = a.neg != b.neg babs := b.abs @@ -312,11 +315,12 @@ func (z *Rat) SetFrac(a, b *Int) *Rat { } // SetFrac64 sets z to a/b and returns z. +// If b == 0, SetFrac64 panics. func (z *Rat) SetFrac64(a, b int64) *Rat { - z.a.SetInt64(a) if b == 0 { panic("division by zero") } + z.a.SetInt64(a) if b < 0 { b = -b z.a.neg = !z.a.neg @@ -328,21 +332,21 @@ func (z *Rat) SetFrac64(a, b int64) *Rat { // SetInt sets z to x (by making a copy of x) and returns z. func (z *Rat) SetInt(x *Int) *Rat { z.a.Set(x) - z.b.abs = z.b.abs[:0] + z.b.abs = z.b.abs.setWord(1) return z } // SetInt64 sets z to x and returns z. func (z *Rat) SetInt64(x int64) *Rat { z.a.SetInt64(x) - z.b.abs = z.b.abs[:0] + z.b.abs = z.b.abs.setWord(1) return z } // SetUint64 sets z to x and returns z. func (z *Rat) SetUint64(x uint64) *Rat { z.a.SetUint64(x) - z.b.abs = z.b.abs[:0] + z.b.abs = z.b.abs.setWord(1) return z } @@ -352,6 +356,9 @@ func (z *Rat) Set(x *Rat) *Rat { z.a.Set(&x.a) z.b.Set(&x.b) } + if len(z.b.abs) == 0 { + z.b.abs = z.b.abs.setWord(1) + } return z } @@ -370,20 +377,13 @@ func (z *Rat) Neg(x *Rat) *Rat { } // Inv sets z to 1/x and returns z. +// If x == 0, Inv panics. func (z *Rat) Inv(x *Rat) *Rat { if len(x.a.abs) == 0 { panic("division by zero") } z.Set(x) - a := z.b.abs - if len(a) == 0 { - a = a.set(natOne) // materialize numerator - } - b := z.a.abs - if b.cmp(natOne) == 0 { - b = b[:0] // normalize denominator - } - z.a.abs, z.b.abs = a, b // sign doesn't change + z.a.abs, z.b.abs = z.b.abs, z.a.abs return z } @@ -411,12 +411,19 @@ func (x *Rat) Num() *Int { } // Denom returns the denominator of x; it is always > 0. -// The result is a reference to x's denominator; it +// The result is a reference to x's denominator, unless +// x is an uninitialized (zero value) Rat, in which case +// the result is a new Int of value 1. (To initialize x, +// any operation that sets x will do, including x.Set(x).) +// If the result is a reference to x's denominator it // may change if a new value is assigned to x, and vice versa. func (x *Rat) Denom() *Int { x.b.neg = false // the result is always >= 0 if len(x.b.abs) == 0 { - x.b.abs = x.b.abs.set(natOne) // materialize denominator + // Note: If this proves problematic, we could + // panic instead and require the Rat to + // be explicitly initialized. + return &Int{abs: nat{1}} } return &x.b } @@ -424,25 +431,20 @@ func (x *Rat) Denom() *Int { func (z *Rat) norm() *Rat { switch { case len(z.a.abs) == 0: - // z == 0 - normalize sign and denominator + // z == 0; normalize sign and denominator z.a.neg = false - z.b.abs = z.b.abs[:0] + fallthrough case len(z.b.abs) == 0: - // z is normalized int - nothing to do - case z.b.abs.cmp(natOne) == 0: - // z is int - normalize denominator - z.b.abs = z.b.abs[:0] + // z is integer; normalize denominator + z.b.abs = z.b.abs.setWord(1) default: + // z is fraction; normalize numerator and denominator neg := z.a.neg z.a.neg = false z.b.neg = false if f := NewInt(0).lehmerGCD(nil, nil, &z.a, &z.b); f.Cmp(intOne) != 0 { z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f.abs) z.b.abs, _ = z.b.abs.div(nil, z.b.abs, f.abs) - if z.b.abs.cmp(natOne) == 0 { - // z is int - normalize denominator - z.b.abs = z.b.abs[:0] - } } z.a.neg = neg } @@ -454,6 +456,8 @@ func (z *Rat) norm() *Rat { // returns z. func mulDenom(z, x, y nat) nat { switch { + case len(x) == 0 && len(y) == 0: + return z.setWord(1) case len(x) == 0: return z.set(y) case len(y) == 0: @@ -509,10 +513,14 @@ func (z *Rat) Sub(x, y *Rat) *Rat { // Mul sets z to the product x*y and returns z. func (z *Rat) Mul(x, y *Rat) *Rat { if x == y { - // a squared Rat is positive and can't be reduced + // a squared Rat is positive and can't be reduced (no need to call norm()) z.a.neg = false z.a.abs = z.a.abs.sqr(x.a.abs) - z.b.abs = z.b.abs.sqr(x.b.abs) + if len(x.b.abs) == 0 { + z.b.abs = z.b.abs.setWord(1) + } else { + z.b.abs = z.b.abs.sqr(x.b.abs) + } return z } z.a.Mul(&x.a, &y.a) @@ -521,7 +529,7 @@ func (z *Rat) Mul(x, y *Rat) *Rat { } // Quo sets z to the quotient x/y and returns z. -// If y == 0, a division-by-zero run-time panic occurs. +// If y == 0, Quo panics. func (z *Rat) Quo(x, y *Rat) *Rat { if len(y.a.abs) == 0 { panic("division by zero") diff --git a/libgo/go/math/big/rat_test.go b/libgo/go/math/big/rat_test.go index 83c5d5c..02569c1 100644 --- a/libgo/go/math/big/rat_test.go +++ b/libgo/go/math/big/rat_test.go @@ -329,18 +329,40 @@ func TestIssue3521(t *testing.T) { t.Errorf("0) got %s want %s", zero.Denom(), one) } - // 1a) a zero value remains zero independent of denominator + // 1a) the denominator of an (uninitialized) zero value is not shared with the value + s := &zero.b + d := zero.Denom() + if d == s { + t.Errorf("1a) got %s (%p) == %s (%p) want different *Int values", d, d, s, s) + } + + // 1b) the denominator of an (uninitialized) value is a new 1 each time + d1 := zero.Denom() + d2 := zero.Denom() + if d1 == d2 { + t.Errorf("1b) got %s (%p) == %s (%p) want different *Int values", d1, d1, d2, d2) + } + + // 1c) the denominator of an initialized zero value is shared with the value x := new(Rat) + x.Set(x) // initialize x (any operation that sets x explicitly will do) + s = &x.b + d = x.Denom() + if d != s { + t.Errorf("1c) got %s (%p) != %s (%p) want identical *Int values", d, d, s, s) + } + + // 1d) a zero value remains zero independent of denominator x.Denom().Set(new(Int).Neg(b)) if x.Cmp(zero) != 0 { - t.Errorf("1a) got %s want %s", x, zero) + t.Errorf("1d) got %s want %s", x, zero) } - // 1b) a zero value may have a denominator != 0 and != 1 + // 1e) a zero value may have a denominator != 0 and != 1 x.Num().Set(a) qab := new(Rat).SetFrac(a, b) if x.Cmp(qab) != 0 { - t.Errorf("1b) got %s want %s", x, qab) + t.Errorf("1e) got %s want %s", x, qab) } // 2a) an integral value becomes a fraction depending on denominator @@ -678,3 +700,29 @@ func BenchmarkRatCmp(b *testing.B) { x.Cmp(y) } } + +// TestIssue34919 verifies that a Rat's denominator is not modified +// when simply accessing the Rat value. +func TestIssue34919(t *testing.T) { + for _, acc := range []struct { + name string + f func(*Rat) + }{ + {"Float32", func(x *Rat) { x.Float32() }}, + {"Float64", func(x *Rat) { x.Float64() }}, + {"Inv", func(x *Rat) { new(Rat).Inv(x) }}, + {"Sign", func(x *Rat) { x.Sign() }}, + {"IsInt", func(x *Rat) { x.IsInt() }}, + {"Num", func(x *Rat) { x.Num() }}, + // {"Denom", func(x *Rat) { x.Denom() }}, TODO(gri) should we change the API? See issue #33792. + } { + // A denominator of length 0 is interpreted as 1. Make sure that + // "materialization" of the denominator doesn't lead to setting + // the underlying array element 0 to 1. + r := &Rat{Int{abs: nat{991}}, Int{abs: make(nat, 0, 1)}} + acc.f(r) + if d := r.b.abs[:1][0]; d != 0 { + t.Errorf("%s modified denominator: got %d, want 0", acc.name, d) + } + } +} diff --git a/libgo/go/math/big/ratconv.go b/libgo/go/math/big/ratconv.go index f29ec98..941139e 100644 --- a/libgo/go/math/big/ratconv.go +++ b/libgo/go/math/big/ratconv.go @@ -123,7 +123,7 @@ func (z *Rat) SetString(s string) (*Rat, bool) { // Multiplications are commutative, so we can apply them in any // order. We only have powers of 2 and 10, and we split powers // of 10 into the product of the same powers of 2 and 5. This - // may reduce the the size of shift/multiplication factors or + // may reduce the size of shift/multiplication factors or // divisors required to create the final fraction, depending // on the actual floating-point value. -- cgit v1.1