From 7f1ef49347e6e1f5a51c9ca3e4f4f617c2317042 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Wed, 23 Oct 2019 14:22:32 -0700 Subject: [release-branch.go1.13] math/big: normalize unitialized denominators ASAP A Rat is represented via a quotient a/b where a and b are Int values. To make it possible to use an uninitialized Rat value (with a and b uninitialized and thus == 0), the implementation treats a 0 denominator as 1. For each operation we check if the denominator is 0, and then treat it as 1 (if necessary). Operations that create a new Rat result, normalize that value such that a result denominator 1 is represened as 0 again. This CL changes this behavior slightly: 0 denominators are still interpreted as 1, but whenever we (safely) can, we set an uninitialized 0 denominator to 1. This simplifies the code overall. Also: Improved some doc strings. Preparation for addressing issue #33792. For #36689. For #33792. Change-Id: I3040587c8d0dad2e840022f96ca027d8470878a0 Reviewed-on: https://go-review.googlesource.com/c/go/+/202997 Run-TryBot: Robert Griesemer TryBot-Result: Gobot Gobot Reviewed-by: Brad Fitzpatrick Reviewed-on: https://go-review.googlesource.com/c/go/+/233322 Run-TryBot: Dmitri Shuralyov Reviewed-by: Emmanuel Odeke --- src/math/big/rat.go | 55 +++++++++++++++++++++++++++-------------------------- 1 file changed, 28 insertions(+), 27 deletions(-) diff --git a/src/math/big/rat.go b/src/math/big/rat.go index 9527b74949..ee8af1456d 100644 --- a/src/math/big/rat.go +++ b/src/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 } @@ -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 (a is part of z!) - } - 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 } @@ -424,25 +424,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 +449,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 +506,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 +522,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") -- cgit v1.2.3-54-g00ecf