Why is big.Rat (and big.Num) designed this way?
Seth Hoenig
Something(x, y *Rat) *Rat.
Which means they are destructive on z. Which means if I need to
remember z's original value, I have to use a dummy value. But not just
one dummy value, one for each function call, less I end up with buggy
code like the following, even though it looks like it should work:
package main
import "fmt"
import "big"
func main() {
fmt.Printf("Sqrt(89.0): %s\n", SqrtBig( big.NewRat(89.0, 1.0)))
}
func SqrtBig( x *big.Rat ) *big.Rat {
return sqrtbig_aux(x, big.NewRat(42.0,1.0), 10)
}
func sqrtbig_aux(x *big.Rat, z *big.Rat, i int) *big.Rat {
if i <= 0 { return z }
temp := big.NewRat(55.0,34.0) // dummy value
fmt.Printf("z: %s, x: %s, i: %d \n", z, x, i)
a := temp.Mul(z,z) // z**2
fmt.Printf("\ta: %s\n", a)
numer := temp.Sub(a, x)
fmt.Printf("\tnumer: %s\n", numer)
denom := temp.Mul( big.NewRat(2.0,1.0), z )
ratio := temp.Quo(numer, denom) // always returns 1 :(
fmt.Printf("\tratio: %s\n", ratio)
z = temp.Sub(z, ratio)
fmt.Printf("\tz: %s\n", z)
return sqrtbig_aux(x, z, i-1)
}
Spot the bug?
I'll give you a big hint, ratio is always == big.NewRat(1.0, 1.0)
Andrew Gerrand
> By "this way", I mean in that they have functions in the form (z *Rat)
> Something(x, y *Rat) *Rat.
>
> Which means they are destructive on z. Which means if I need to
> remember z's original value, I have to use a dummy value. But not just
> one dummy value, one for each function call, less I end up with buggy
> code like the following, even though it looks like it should work:
For a start, this doesn't need to be recursive. It can be a loop. Once
you think of it this way, it makes sense to create temporary big.Rats
that are allocated only once. The design of big allows you to manage
memory allocation so that mathematical operations can be as fast as
possible.
Here's an alternate implementation that I think is pretty easy to read:
package main
import (
"big"
"fmt"
)
func main() {
fmt.Println(SqrtBig(big.NewRat(100.0, 1.0)))
}
func SqrtBig(x *big.Rat) *big.Rat {
z := big.NewRat(10.0, 1.0) // TODO: pick better starting point
a := big.NewRat(0, 0) // temporary
num, den, quo := big.NewRat(0, 0), big.NewRat(0, 0), big.NewRat(0, 0)
for i := 10; i > 0; i-- {
a.Mul(z, z)
num.Sub(a, x)
den.Mul(big.NewRat(2.0, 1.0), z)
quo.Quo(num, den)
a.Sub(z, quo)
z.Set(a)
}
return z
}
Andrew
Andrew Gerrand
> den.Mul(big.NewRat(2.0, 1.0), z)
Just noticed: this big.NewRat(2.0, 1.0) should be created outside the loop.
Andrew
Evan Shaw
> Which means they are destructive on z. Which means if I need to
> remember z's original value, I have to use a dummy value.
I agree that big's interface could be better, but I don't really
understand this particular complaint. To me, this is kind of like
complaining about the statement
z = x + y
because z's old value is lost. If you want to keep z's current value,
then don't assign it a new one. Similarly, if you want to keep the
value of a big.Int, then don't call any of its destructive functions.
The analogous statement with big is
z.Add(x, y)
Note that it's not necessary to assign the return of this to anything
because it's just returning z. In fact, to assign it to anything other
than z would be misleading. Maybe that's what you're complaining
about, and if that's the case, I can understand. An easy way of
improving big's interface might be to make Add and friends have no
return at all.
If you're suggesting that every arithmetic function return a newly
allocated big.Int (or big.Rat), there's some history there. big
replaces a package called bignum, which did return a new object for
every function called. It was also significantly slower because the
caller had no way of preventing unnecessary allocations.
- Evan
Cory Mainwaring
Seth Hoenig
z.Add(x, y)
Note that it's not necessary to assign the return of this to anything
because it's just returning z. In fact, to assign it to anything other
than z would be misleading
Evan Shaw
I think you're misunderstanding what I'm saying. I realize that Add is
a destructive function. I'm saying that writing
r := z.Add(x, y)
is misleading because it's hard to tell that the value of z is
changing in this statement.
What I'm telling you is that if you don't want to lose the value of z,
then don't bring z into the picture at all. Just say
r := new(big.Int).Add(x, y)
- Evan
Seth Hoenig
Evan Shaw
> And how is that any more efficient than if the function were non
> destructive?
It's not in this case. If you want to keep around all your old values,
then you have no choice but to allocate new ones. The real benefit is
when you *don't* need to keep around your old values. If I don't care
about the old value of z. I can reuse its storage and avoid an
allocation.
The bignum interface, on the other hand, would give the caller no
choice and allocate every time.
- Evan
Clark Gaebel
a.Add(b); // a = a + b -> No return value.
--
Regards,
-- Clark
Cory Mainwaring
Evan Shaw
> Then why not design it like so?
>
> a.Add(b); // a = a + b -> No return value.
That would probably be better than what's there right now. However,
you might consider returning a pointer to a to allow things like this:
a.Add(b).Mul(c)
Then you have the same confusion that's there now, of course.
- Evan
Clark Gaebel
It would be an extremely explicit API, but in the cases you need bignum
(such as implementing RSA), being explicit is often better than having
subtleties.
--
Regards,
-- Clark
Russ Cox
> And how is that any more efficient than if the function were non
> destructive?
Like Evan said, z.Something(x, y) should be thought of as
z = x Something y
If z appears on the left side, it gets overwritten.
If it appears on the right, it does not.
It's a familiar model for many programmers.
The claim that you have to use a dummy value
to remember z's original value is hard to understand:
the same is true of ordinary assignment. (If even that
bothers you, you might look into Haskell instead of Go.)
As for why you don't write
z.Equals(x.Something(y))
the answer is that this style generates garbage at
an amazing rate, and for any serious use of bignums
(like crypto) you need to control that rate to get reasonable
performance. There was a package with that interface,
called "bignum" and then "exp/bignum". It was too slow.
You can find it in the repository history if you're curious
to play with it.
> If anything, it's just hideous (almost to the point of obfuscated) code
> where it could be much cleaner.
Don't take this the wrong way, but just because you wrote
some hideous code doesn't mean that it's impossible to
write nice code. Almost everyone who starts programming
with big (myself included) starts out with hideous code,
because it takes a while to internalize "write the assignments
and translate to method calls".
If nothing else, instead of writing
a := temp.Mul(z, z)
a = temp.Mul(x, y)
it's almost always better to write
a := new(big.Rat).Mul(z, z)
a.Mul(x, y)
(The two lines have different translations because of := vs =.)
That is, treat each big.Rat (or big.Int) as its own variable and
only ever use one of those two forms and you'll get readable
code without the kinds of subtle bugs that you pointed out.
Russ
Tianyi Cui
> Don't take this the wrong way, but just because you wrote
> some hideous code doesn't mean that it's impossible to
> write nice code. Almost everyone who starts programming
> with big (myself included) starts out with hideous code,
> because it takes a while to internalize "write the assignments
> and translate to method calls".
method calls" way. But I think we need the a+=b assignment
style API too along with the current a=b+c assignment style APIs.
So I think either we add API like a.Inc(b) as a+=b or in a.Add(b,c)
we check whether a and b are actually the same object and do
some optimization.
Tianyi Cui
roger peppe
> we check whether a and b are actually the same object and do
> some optimization.
what optimization are you thinking of here?
roger peppe
> So add a Duplicate method as well and then you can write:
>
> a.Duplicate().Add(b).Mul(c)
FWIW, a.Duplicate() would be equivalent to:
new(big.Int).Set(a)
in the current API.
BTW, i don't understand what the problem is with
a.Add(a, b)
John Asmuth
thread has coined them, operations.
For instance "x.Add(y)" updates x's value. "x.Plus(z)" does not. Both
of them are included because they are both obvious use cases that
people might want for different situations.
- John
On Aug 11, 10:18 pm, Clark Gaebel <cg.wowus...@gmail.com> wrote:
> Then why not design it like so?
>
> a.Add(b); // a = a + b -> No return value.
>
> On 08/11/10 22:13, Evan Shaw wrote:
>
Eleanor McHugh
So add a Duplicate method as well and then you can write:
a.Duplicate().Add(b).Mul(c)
Or maybe use some closure magic:
a.UseInvariant(func(i *bigint) *bigint { return i.Add(b).Mul(c) })
where UseInvariant would create a copy of a and pass that into the closure.
I think I'll have to play with that latter idea in GoLightly as there are quite a few places where I use Duplicate() which might work nicer with UseInvariant() - although the method could probably do with a better name...
Ellie
Eleanor McHugh
Games With Brains
http://feyeleanor.tel
----
raise ArgumentError unless @reality.responds_to? :reason
Russ Cox
> we check whether a and b are actually the same object and do
> some optimization.
I believe a.Add(a, b) already does this.
Russ
Sonia Keys
> ...
> z := big.NewRat(10.0, 1.0) // TODO: pick better starting point
> a := big.NewRat(0, 0) // temporary
> num, den, quo := big.NewRat(0, 0), big.NewRat(0, 0), big.NewRat(0, 0)
> for i := 10; i > 0; i-- {
> a.Mul(z, z)
> num.Sub(a, x)
> den.Mul(big.NewRat(2.0, 1.0), z)
> quo.Quo(num, den)
> a.Sub(z, quo)
> z.Set(a)
> }
> return z
>
> }
>
> Andrew
First, z.Set(a) is not needed. The line before can simply say
z.Sub(z, quo).
Then a few little clean ups: I gave the function a more specific
name. Big is the package name, this function takes the square root of
a Rat.
The remaining floating point constants bugged me. These functions
take int64s and it's distracting, if not misleading, to have those .0s
on the end.
As Andrew noted, creating the constant 2 can be moved out of the
loop. In fact, it probably makes sense to move it all the way out of
the function:
var two *big.Rat
func init() {
two = big.NewRat(2, 1)
}
func SqrtRat(x *big.Rat) *big.Rat {
z := big.NewRat(10, 1) // TODO: pick better starting point
num, den, quo := big.NewRat(0, 0), big.NewRat(0, 0),
big.NewRat(0, 0)
for i := 10; i > 0; i-- {
a.Mul(z, z)
num.Sub(a, x)
quo.Quo(num, den)
z.Sub(z, quo)
}
return z
}
Next, multiple instances of big.NewRat(0, 0), looks messy to me.
new(big.Rat) would be a little better, but I like just declaring the
variables, especially when some of them don't need any special
initialization.
var two big.Rat
func init() {
two.SetInt64(2)
}
func SqrtRat(x *big.Rat) *big.Rat {
var z, a, num, den, quo big.Rat
z.SetInt64(10) // TODO: pick better starting point
num.Sub(&a, x)
den.Mul(&two, &z)
quo.Quo(&num, &den)
z.Sub(&z, &quo)
}
return &z
}
This doesn't save any allocations. I believe it does exactly the same
thing. The trade off is simply the new()s for the &s. Some &s go
away though, if the operations are chained together, which is of
course a benefit of having methods return values.
The function is looking pretty compact at this point!
func SqrtRat(x *big.Rat) *big.Rat {
var z, a, num, den, quo big.Rat
z.SetInt64(10) // TODO: pick better starting point
den.Mul(&two, &z)))
}
return &z
}
I don't think chaining has been mentioned yet in this discussion. You
may or may not find this version easy to read, but many people who
code formulas like to put multiple operations--a complete formula, if
possible--on one line. The proposals to have big methods not return a
value would prevent this.
To actually save a few allocations, some of the variables can be
reused. This comes at the expense of readability as some variables
are no longer used for a single purpose. I reuse 'a' for the
numerator, and use the same variable for denominator and quotient,
calling it simply b.
Also I added a starting point computation, so the function is starting
to grow again:
func SqrtRat(x *big.Rat) *big.Rat {
var z, a, b big.Rat
var ns, ds big.Int
ni, di := x.Num(), x.Denom()
z.SetFrac(ns.Rsh(ni, uint(ni.BitLen())/2), ds.Rsh(di,
uint(di.BitLen())/2))
for i := 10; i > 0; i-- { //TODO: better termination
criteria?
z.Sub(&z, b.Quo(a.Sub(a.Mul(&z, &z), x), b.Mul(&two,
&z)))
}
return &z
}
There's more that could be done. I think the formula can be
simplified a bit without losing anything. Exact answers aren't caught
early, and for approximate answers, 10 looks like an arbitrary point
to terminate.
Sonia
Seth Hoenig
Next question: how do I go from the result:
35216337509483420567111756924245690762980988784016109620462189046868530455298318575488327742602117614928498876569011396594860542203966139657369263422887255411218860185649756037007733589302315038420900482401650105057839948979320142241048013322759099668308113502962890830727936882871586598853705589727481153801347569090265604317628480946267713255374785929850956988909408298926325837205624538833115186441866924443932916135282025282728937888085896812178500655204223515879876774582786666611741637322335882557740818151284210643518641436284668009689938480890214307066757703743789419100206813331990297014536334758821151095575996089030695665393821189385035443580503171374889573892587676091318715982987091649425770219363167353879292932892051266598505436929005206840122129079297546549342099101815797895822200288243638436446616554660321416355024016085195328654339097204180586841994870559158828935412980160263121253860199143418920184422042584337787346182643609391649008118820543369376984450763987356826732409199863710659948490612963071904425578497/3732924310164088085626343245937031764559875133139710047158871960968574251424682827120884638674451973408007569947879344139588109797757538389727313925656009970090105740747240706242137593770943697202672658398736376678123785429651856144501397419635950140468546021501382194229137838832604850687118475283300795481574486661279709457690991740772344080279674764449181284061885735859127541666294745935886515359893049439724069172966362899142355317428667946916680398188828089422970846237486373029740254259621259216255956105056069237278349271106414703201026888331290373333272270655366251381610560759007499042092737148026713329728069853351147902629324073140064881873217559562713670684922336255110700187913703531476642410528887937617606152726538826056103463421827198025552351577574482207047387184542968463492157882249261733529430868807801057759983791731980921542743796362182105004301637067699355994810468141147213377656102863454888843782533364538956652700292902038121095619893290257300821592289266588585537729190562085306519336786743407157044121555
To a more readable decimal output?
Python's interpreter says the expression pasted is equivalent to:
9.433981132056605
Andrew Gerrand
> Next question: how do I go from the result:
>
> To a more readable decimal output?
>
> Python's interpreter says the expression pasted is equivalent to:
> 9.433981132056605
Use the FloatString function:
http://golang.org/pkg/big/#Rat.FloatString
Andrew