Issue 1250043: code review 1250043: big: Add Rat type (Closed)
|
Created:
14 years, 10 months ago by eds Modified:
14 years, 10 months ago Reviewers:
CC:
gri, golang-dev Visibility:
Public. |
Descriptionbig: Add Rat type
Implementations are pretty rough and simple at this point, but it's a start.
Patch Set 1 #Patch Set 2 : code review 1250043: big: Add Rat type #Patch Set 3 : code review 1250043: big: Add Rat type #Patch Set 4 : code review 1250043: big: Add Rat type #
Total comments: 27
Patch Set 5 : code review 1250043: big: Add Rat type #
Total comments: 15
Patch Set 6 : code review 1250043: big: Add Rat type #Patch Set 7 : code review 1250043: big: Add Rat type #
MessagesTotal messages: 11
Hello gri (cc: golang-dev@googlegroups.com), I'd like you to review this change.
Sign in to reply to this message.
On Thu, May 20, 2010 at 8:32 PM, <chickencha@gmail.com> wrote: > Reviewers: gri, > > Message: > Hello gri (cc: golang-dev@googlegroups.com), > > I'd like you to review this change. > > > Description: > big: Add Rat type > > Implementations are pretty rough and simple at this point, but it's a > start. > > Please review this at http://codereview.appspot.com/1250043/show > > Affected files: > M src/pkg/big/Makefile > M src/pkg/big/nat.go > A src/pkg/big/rat.go > A src/pkg/big/rat_test.go > > > I held off on Num and Denom since I don't know whether to return a pointer to the numbers or a copy. I'm leaning towards a copy. I'm also not sure about the behavior of FloatString. For example, if your number's 1/1 and you specify 3 digits of precision, would you expect the output to be: 1 1.00 1.000 I opted for the first, but that may not be what people expect. - Evan
Sign in to reply to this message.
Some initial comments. More to come tomorrow. http://codereview.appspot.com/1250043/diff/13001/14001 File src/pkg/big/Makefile (right): http://codereview.appspot.com/1250043/diff/13001/14001#newcode10 src/pkg/big/Makefile:10: rat.go\ i'd make this alphabetical http://codereview.appspot.com/1250043/diff/13001/14003 File src/pkg/big/rat.go (right): http://codereview.appspot.com/1250043/diff/13001/14003#newcode11 src/pkg/big/rat.go:11: // A Rat represents a quotient a/b of arbitrary precision in reduced form. leave away "in reduced form" (that's implementation). Also, the zero value for a Rat is not a legal Rat (it's 0/0) - should mention that. http://codereview.appspot.com/1250043/diff/13001/14003#newcode13 src/pkg/big/rat.go:13: a Int yes, this is a better choice than a *Int http://codereview.appspot.com/1250043/diff/13001/14003#newcode19 src/pkg/big/rat.go:19: func NewRat(a int64, b uint64) *Rat { I found that I need more than these setters. In my code I have now the ones below (and I use them in hilbert.go): // Set sets z to x and returns z. func (z *Rat) SetInt64(x int64) *Rat // SetFrac64 sets z to a/b and returns z. func (z *Rat) SetFrac64(a, b int64) *Rat // Set sets z to x (by making a copy of x) and returns z. func (z *Rat) SetInt(x *Int) *Rat // SetFrac sets z to a/b and returns z. func (z *Rat) SetFrac(a, b *Int) *Rat // Set sets z to x (by making a copy of x if necessary) and returns z. func (z *Rat) Set(x *Rat) *Rat (Also, I think it's better not to mix int64 and uint64 in the interface - it's already complicated enough). http://codereview.appspot.com/1250043/diff/13001/14003#newcode43 src/pkg/big/rat.go:43: a, b := x, y I believe you need to make a copy here to be safe: var a, b nat a = a.set(x) b = b.set(y) (my hilbert code fails w/o this). http://codereview.appspot.com/1250043/diff/13001/14003#newcode60 src/pkg/big/rat.go:60: if len(z.a.abs) == 0 { I would move this before the computation of f: if len(z.a.abs) == 0 { // z == 0 z.a.neg = false // normalize sign z.b = nat{1} return z } The other operations will keep the sign normalized. http://codereview.appspot.com/1250043/diff/13001/14003#newcode70 src/pkg/big/rat.go:70: z.neg = x.neg z.neg = len(z.abs) > 0 && x.neg // 0 has no sign http://codereview.appspot.com/1250043/diff/13001/14003#newcode91 src/pkg/big/rat.go:91: return x1.cmp(y1) If x and y are negative (say x = -2, y = -1), this is wrong: x1 == 2, y1 == 1 and x1 > y1; but x < y. I would leave away the optimization and just write: return mulNat(x.a, y.b).Cmp(mulNat(y.a, x.b)) and be done with it http://codereview.appspot.com/1250043/diff/13001/14003#newcode95 src/pkg/big/rat.go:95: // Add computes z = x+y and returns z. // Add sets z to the sum x+y and returns z. http://codereview.appspot.com/1250043/diff/13001/14003#newcode107 src/pkg/big/rat.go:107: // Sub computes z = x-y and returns z. // Sub sets z to the difference x-y and returns z. http://codereview.appspot.com/1250043/diff/13001/14003#newcode119 src/pkg/big/rat.go:119: // Mul computes z = x*y and returns z. // Mul sets z to the product x*y and returns z. http://codereview.appspot.com/1250043/diff/13001/14003#newcode127 src/pkg/big/rat.go:127: // Quo computes z = x/y for y != 0 and returns z. // Quo sets z to the quotient x/y and returns z. http://codereview.appspot.com/1250043/diff/13001/14003#newcode131 src/pkg/big/rat.go:131: panic("division by zero") no need for this check - if y is zero, the panic will be raised as a result of norm() http://codereview.appspot.com/1250043/diff/13001/14003#newcode141 src/pkg/big/rat.go:141: // Neg computes z = -x and returns z. // Neg sets z to -x (by making a copy of x if necessary) and returns z. (matching the style in int.go) http://codereview.appspot.com/1250043/diff/13001/14003#newcode149 src/pkg/big/rat.go:149: // Set sets z to x. // Set sets z to x (by making a copy of x if necessary) and returns z. (matching the style in int.go) http://codereview.appspot.com/1250043/diff/13001/14003#newcode158 src/pkg/big/rat.go:158: // number. 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 decimal number "a.b". If the operation failed, z is unchanged. http://codereview.appspot.com/1250043/diff/13001/14003#newcode159 src/pkg/big/rat.go:159: func (z *Rat) SetString(s string) (*Rat, bool) { func (z *Rat) SetString(s string) (res *Rat, ok bool) { res = z http://codereview.appspot.com/1250043/diff/13001/14003#newcode160 src/pkg/big/rat.go:160: var r bool no need for this http://codereview.appspot.com/1250043/diff/13001/14003#newcode163 src/pkg/big/rat.go:163: z.a.neg = false just return (no need to change z, ok is set to false by default) http://codereview.appspot.com/1250043/diff/13001/14003#newcode176 src/pkg/big/rat.go:176: _, r = z.a.SetString(s, 10) if _, ok = z.a.SetString(s, 10); !ok { return } http://codereview.appspot.com/1250043/diff/13001/14003#newcode178 src/pkg/big/rat.go:178: return z, r return z, true http://codereview.appspot.com/1250043/diff/13001/14003#newcode180 src/pkg/big/rat.go:180: _, r = z.a.SetString(s[0:sep], 10) same here: if _, ok = ... http://codereview.appspot.com/1250043/diff/13001/14003#newcode184 src/pkg/big/rat.go:184: return z, r return z.norm(), true http://codereview.appspot.com/1250043/diff/13001/14003#newcode188 src/pkg/big/rat.go:188: _, r = z.a.SetString(s, 10) if _, ok := ... { return } http://codereview.appspot.com/1250043/diff/13001/14003#newcode192 src/pkg/big/rat.go:192: z.norm() return z.norm(), true http://codereview.appspot.com/1250043/diff/13001/14003#newcode197 src/pkg/big/rat.go:197: // String returns a string representation of z in the form "a/b". Perhaps it should return just a if b == 1?
Sign in to reply to this message.
For your reference, attached is my (less complete version). You may be able
to borrow some stuff.
I agree that the choice of representation for Rat using an Int instead of
*Int is better (my code is still using *Int).
- Robert
On // Copyright 2010 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.
// This file implements multi-precision rational numbers.
package big
// A Rat represents a quotient a/b of arbitrary precision.
type Rat struct {
a *Int // numerator TODO(gri) should use Int instead of *Int
b nat // denominator
}
func gcd(x, y nat) nat {
// Euclidean algorithm.
var a, b nat
a = a.set(x)
b = b.set(y)
for len(b) != 0 {
var q, r nat
_, r = q.div(r, a, b)
a = a.set(b)
b = b.set(r)
}
return a
}
func (z *Rat) norm() *Rat {
if len(z.a.abs) == 0 {
// z == 0
z.a.neg = false // normalize sign
z.b = nat{1}
return z
}
// z != 0
f := gcd(z.a.abs, z.b)
if f.cmp(natOne) != 0 {
z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f)
z.b, _ = z.b.div(nil, z.b, f)
}
return z
}
func mulNat(x *Int, y nat) *Int {
var z Int
z.abs = z.abs.mul(x.abs, y)
z.neg = len(z.abs) > 0 && x.neg // 0 has no sign
return &z
}
func (x *Rat) IsInt() bool {
return len(x.b) == 1 && x.b[0] == 1
}
// NewRat allocates and returns a new zero Rat value.
// TODO(gri) remove - not needed with different Rat representation
func NewRat() *Rat {
return &Rat{&Int{}, nat{1}}
}
// Set sets z to x and returns z.
func (z *Rat) SetInt64(x int64) *Rat {
z.a.SetInt64(x)
z.b = nat{1}
return z
}
// SetFrac64 sets z to a/b and returns z.
func (z *Rat) SetFrac64(a, b int64) *Rat {
aa := NewInt(a)
bb := NewInt(b)
if bb.neg {
aa.neg = !aa.neg // norm() normalizes sign
}
return (&Rat{aa, bb.abs}).norm()
}
// Set 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 = nat{1}
return z
}
// SetFrac sets z to a/b and returns z.
func (z *Rat) SetFrac(a, b *Int) *Rat {
z.a.Set(a)
z.b = z.b.set(b.abs)
if b.neg {
z.a.neg = !z.a.neg // norm() normalizes sign
}
return z.norm()
}
// Set sets z to x (by making a copy of x if necessary) and returns z.
func (z *Rat) Set(x *Rat) *Rat {
z.a.Set(x.a)
z.b = z.b.set(x.b)
return z
}
// Neg sets z to -x (by making a copy of x if necessary) and returns z.
func (z *Rat) Neg(x *Rat) *Rat {
z.a.Neg(x.a)
z.b = z.b.set(x.b)
return z
}
// Num returns the numerator of x; it may be <= 0.
// The result is a reference to x's numerator; it
// may change if a new value is assigned to x.
func (x *Rat) Num() *Int {
return x.a
}
// Demom returns the denominator of x; it is always > 0.
// The result is a reference to x's denominator; it
// may change if a new value is assigned to x.
func (x *Rat) Denom() *Int {
return &Int{false, x.b}
}
// Add sets z to the sum x+y and returns z.
func (z *Rat) Add(x, y *Rat) *Rat {
a1 := mulNat(x.a, y.b)
a2 := mulNat(y.a, x.b)
z.a.Add(a1, a2)
z.b = z.b.mul(x.b, y.b)
return z.norm()
}
// Sub sets z to the difference x-y and returns z.
func (z *Rat) Sub(x, y *Rat) *Rat {
a1 := mulNat(x.a, y.b)
a2 := mulNat(y.a, x.b)
z.a.Sub(a1, a2)
z.b = z.b.mul(x.b, y.b)
return z.norm()
}
// Mul sets z to the product x*y and returns z.
func (z *Rat) Mul(x, y *Rat) *Rat {
z.a.Mul(x.a, y.a)
z.b = z.b.mul(x.b, y.b)
return z.norm()
}
// Quo sets z to the quotient x/y and returns z.
func (z *Rat) Quo(x, y *Rat) *Rat {
a := mulNat(x.a, y.b)
b := mulNat(y.a, x.b)
if b.neg {
a.neg = !a.neg // norm() normalizes sign
}
z.a = a
z.b = b.abs
return z.norm()
}
// Cmp compares x and y and returns:
//
// -1 if x < y
// 0 if x == y
// +1 if x > y
//
func (x *Rat) Cmp(y *Rat) int {
return mulNat(x.a, y.b).Cmp(mulNat(y.a, x.b))
}
func (x *Rat) String() string {
s := x.a.String()
if !x.IsInt() {
s += "/" + x.b.string(10)
}
return s
}
Sign in to reply to this message.
I think I've addressed everything so far except for one comment. http://codereview.appspot.com/1250043/diff/13001/14003 File src/pkg/big/rat.go (right): http://codereview.appspot.com/1250043/diff/13001/14003#newcode131 src/pkg/big/rat.go:131: panic("division by zero") On 2010/05/21 03:14:00, gri wrote: > no need for this check - if y is zero, the panic will be raised as a result of > norm() Not with the current code. gcd will exit before it tries to divide a by b and nothing in norm() tries to divide by zero after that.
Sign in to reply to this message.
Looks pretty good. http://codereview.appspot.com/1250043/diff/13002/19003 File src/pkg/big/rat.go (right): http://codereview.appspot.com/1250043/diff/13002/19003#newcode16 src/pkg/big/rat.go:16: } I think we need to provide accessors (num(), denom()) to the components of the Rat. As it is, there's no way to take a Rat() apart except for the String conversions. I think it is fine to not make a copy as long as it is clear in the documentation. Most of the time, one will use those values as input to other operations which in general do not modify the inputs. If one uses the values to Set another value, a copy is made at that time. http://codereview.appspot.com/1250043/diff/13002/19003#newcode37 src/pkg/big/rat.go:37: z.b = z.b.setUint64(uint64(b)) this is not right: if b == -1, uint64(b) is (1<<64)-1 which is incorrect (should be caught by the test suite) http://codereview.appspot.com/1250043/diff/13002/19003#newcode115 src/pkg/big/rat.go:115: these empty lines in Add, Sub, Quo can probably go - there's no similar grouping in the other short functions http://codereview.appspot.com/1250043/diff/13002/19003#newcode175 src/pkg/big/rat.go:175: // If the operation failed, z is unchanged. perhaps better: If SetString fails, z remains unchanged. http://codereview.appspot.com/1250043/diff/13002/19003#newcode176 src/pkg/big/rat.go:176: func (z *Rat) SetString(s string) (res *Rat, ok bool) { res = z (At least I read the description as z is always returned - seems simpler in the semantics. The corresponding Int.SetString should do the same - I'll change it.) http://codereview.appspot.com/1250043/diff/13002/19003#newcode183 src/pkg/big/rat.go:183: if sep == -1 { if sep < 0 (An index < 0 is clearly not valid; testing against -1 requires more knowledge about strings.Index; testing against 0 also tends to generate shorter code) http://codereview.appspot.com/1250043/diff/13002/19003#newcode186 src/pkg/big/rat.go:186: if sep == -1 { if sep < 0 http://codereview.appspot.com/1250043/diff/13002/19003#newcode197 src/pkg/big/rat.go:197: z.b, _, _ = z.b.scan(s[sep+1:], 10) this operation may fail as well http://codereview.appspot.com/1250043/diff/13002/19003#newcode207 src/pkg/big/rat.go:207: z.b = z.b.expNN(natTen, nat{Word(sep)}, nil) /sep/len(s)-sep/ and get rid of the assignment before (sep is not the position of the separator anymore) http://codereview.appspot.com/1250043/diff/13002/19003#newcode226 src/pkg/big/rat.go:226: var s string i'd move this declaration before it's first use, before the if z.a.neg. Maybe use s := "" http://codereview.appspot.com/1250043/diff/13002/19004 File src/pkg/big/rat_test.go (right): http://codereview.appspot.com/1250043/diff/13002/19004#newcode15 src/pkg/big/rat_test.go:15: setStringTest{"0", "0"}, add case "-0" to test normalization http://codereview.appspot.com/1250043/diff/13002/19004#newcode20 src/pkg/big/rat_test.go:20: setStringTest{"-1/5", "-1/5"}, - should also have cases that fail - add some larger values as well http://codereview.appspot.com/1250043/diff/13002/19004#newcode97 src/pkg/big/rat_test.go:97: out string s/out/z/ ? then it would match the function signature and the conventions http://codereview.appspot.com/1250043/diff/13002/19004#newcode104 src/pkg/big/rat_test.go:104: expected, _ := NewRat(0, 1).SetString(test.out) z, _ := NewRat... (make it symmetric) http://codereview.appspot.com/1250043/diff/13002/19004#newcode113 src/pkg/big/rat_test.go:113: The Add/Sub tests and the Mul/Quo tests are completely symmetric. You should need only one data set for Add/Sub and one for Mul/Quo. You could even have a single data set containing the values x, y, x+y, x*y (perhaps with a flag to exclude the div-0 cases)
Sign in to reply to this message.
PS: For SetString it might be better to say that if it fails, the value of z is undefined. This permits a simpler implementation. - gri
Sign in to reply to this message.
Hello gri (cc: golang-dev@googlegroups.com), Please take another look.
Sign in to reply to this message.
LGTM (I guess you didn't want to make the changes to the tests?) On Fri, May 21, 2010 at 3:40 PM, <chickencha@gmail.com> wrote: > Hello gri (cc: golang-dev@googlegroups.com), > > Please take another look. > > > > http://codereview.appspot.com/1250043/show >
Sign in to reply to this message.
*** Submitted as http://code.google.com/p/go/source/detail?r=53bc90805d29 *** big: Add Rat type Implementations are pretty rough and simple at this point, but it's a start. R=gri CC=golang-dev http://codereview.appspot.com/1250043 Committer: Robert Griesemer <gri@golang.org>
Sign in to reply to this message.
On Fri, May 21, 2010 at 6:14 PM, Robert Griesemer <gri@golang.org> wrote: > LGTM > (I guess you didn't want to make the changes to the tests?) D'oh, I got so caught up with the other stuff that I didn't even see those. I'll submit another CL.
Sign in to reply to this message.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
