Code review - Issue 6930059: code review 6930059: math/big: add Rat.{,Set}Float64 methods for IEEE 754 co...https://codereview.appspot.com/2013-01-28T23:00:27+00:00rietveld
Message from unknown
2012-12-13T01:17:26+00:00adonovanurn:md5:518536ea6718051b6f5c26a3297ed1da
Message from unknown
2012-12-13T01:17:36+00:00adonovanurn:md5:82be2557810dd0dba15708eb9dc4ebe7
Message from gri@golang.org
2012-12-13T01:52:05+00:00griurn:md5:c53122657da1215f06a6e858caecfa4f
Haven't thought through this is detail yet, but here some prelim. feedback.
Please pay attention particularly to the re-use of the underlying slices by using the appropriate set functions. We have gone through a lot of pain to get meth/big to where it is. The reason for re-using the underlying memory is performance (the first implementation didn't do it and was _much_ slower overall). It may not matter for a single function, but it does matter overall when the function is used in a larger algorithm.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode35
src/pkg/math/big/rat.go:35: panic("SetFloat requires finite value")
SetFloat64
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode35
src/pkg/math/big/rat.go:35: panic("SetFloat requires finite value")
on that note, I am wondering if this is a good choice. alternatively, one might return nil. as it is, a client will have to check anyway, so why not provide the result? also, if the client doesn't pay attention, it will die with a null ptr exception when the result is used. about the same.
so: return nil ?
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode37
src/pkg/math/big/rat.go:37: if f == 0.0 {
f == 0
seems good enough - we are in Go after all
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode38
src/pkg/math/big/rat.go:38: z.a, z.b = Int{}, *intOne
that's not how we do this in this package - you throw away whatever memory is hanging of z by doing this
use the appropriate Set function
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode43
src/pkg/math/big/rat.go:43: const SmallestNormal = 2.2250738585072014e-308 // 2**-1022
this code is also in math/bits.go - should at least mention this in a comment
(even better if we can find a way some of this can be shared) - it's subtle enough that we don't want to have random copies all over the place
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode52
src/pkg/math/big/rat.go:52: mantissa := (1 << 52) | (bits & 0xFFFFFFFFFFFFF)
The constants 52, 1023, etc. should be at least declared as constants (or perhaps computed from other constants) if we can't import them. same for 0x7ff.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode57
src/pkg/math/big/rat.go:57: z.b = *intOne
use Set function so we don't throw away underlying memory
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode60
src/pkg/math/big/rat.go:60: z.b.abs = z.b.abs.shl(z.b.abs, uint(shift))
use set functions
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode69
src/pkg/math/big/rat.go:69: // Preconditions: b is nonzero; a and b have no common factors.
s/nonzero/non-zero/
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode97
src/pkg/math/big/rat.go:97: expt := alen - blen
s/expt/exp/ please
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode117
src/pkg/math/big/rat.go:117: if expt > 1024 {
switch {
case expt > 1024:
...
case expt < -1023:
if neg {
return -1
}
return 0
}
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode148
src/pkg/math/big/rat.go:148: (uint64((expt+1023)&0x7FF) << 52) | mantissa)
one line please
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode165
src/pkg/math/big/rat.go:165: exact = false
just return
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode172
src/pkg/math/big/rat.go:172: exact = z2.Cmp(z) == 0
I'd do:
if z2.Cmp(z) == 0 {
exact = true
}
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go
File src/pkg/math/bits.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go#newcode40
src/pkg/math/bits.go:40: func IsFinite(f float64) bool {
why not use IsInf?
Message from remyoudompheng@gmail.com
2012-12-13T07:37:38+00:00remyoudomphengurn:md5:2f58dc01f623e17e64bcd657154c5a78
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode53
src/pkg/math/big/rat.go:53: exp := int((bits>>52)&0x7FF) - 1023
mantissa := bits & (1<<52-1) (counting these F's is crazy)
exp := int(bits>>52 & 0x7ff)
switch exp {
case 0x7ff:
// NaN or infinite
...
case 0:
// denormal
exp -= 1023
default:
mantissa |= 1<<52
exp -= 1023
}
and remove the special cases above, and no need to change math package interface.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode82
src/pkg/math/big/rat.go:82: // The result contains mantissa A/B and exponent e.
Sorry but this algorithm is incorrect. It breaks at the simplest testcase:
func TestFloat64(t *testing.T) {
const U = 1<<60 - 1
z := new(Rat).SetInt64(U)
v, _ := z.Float64()
if v != 1<<60 {
t.Errorf("got %b, expected %b", v, float64(1<<60))
}
}
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode146
src/pkg/math/big/rat.go:146: mantissa := uint64(q[0] & 0xfffffffffffff) // 52 bits
This line doesn't compile at all.
Here Word is 32 bit.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat_test.go
File src/pkg/math/big/rat_test.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat_test.go#newcode508
src/pkg/math/big/rat_test.go:508: // TODO(adonovan): is this ok? Or should I copy the file, or even
I'm not sure testfp.txt is a good input file for tests.
A table driven test + use testing/quick to check
* z.SetFloat64(f).Float64() == f
* x := z.Float64, x1, x2 = prevFloat64(x), nextFloat64(x)
// use SetFloat64 and big.Rat arithmetic to check that x is closest to z as specified.
Message from remyoudompheng@gmail.com
2012-12-13T07:44:05+00:00remyoudomphengurn:md5:8bf9d644c9ef716a67d7250bd9dd1c06
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode82
src/pkg/math/big/rat.go:82: // The result contains mantissa A/B and exponent e.
After correcting please check that your function rounds correctly:
1<<253 - 1<<199 + 1 -> 1<<253
1<<253 - 1<<199 - 1 -> previous float64 before 1<<253
(1<<253 - 1<<200 I guess).
And you should specify what happens when the rat is halfway.
Message from rsc@golang.org
2012-12-13T14:41:58+00:00rscurn:md5:29444ff21fbdcc441ce43a9300be87d4
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat_test.go
File src/pkg/math/big/rat_test.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat_test.go#newcode508
src/pkg/math/big/rat_test.go:508: // TODO(adonovan): is this ok? Or should I copy the file, or even
You can read the file directly, that's fine. As for using it, what I had intended (but not expressed well) was to use the decimal -> binary conversions as rat -> binary conversions by building fractions with appropriate denominators. For example the file contains
# Table 1: Stress Inputs for Conversion to 53-bit Binary, < 1/2 ULP
float64 %b 5e+125 6653062250012735p+365
float64 %b 69e+267 4705683757438170p+841
float64 %b 999e-026 6798841691080350p-129
In the strconv package that says to try strconv.ParseFloat("5e+125", 64) and make sure you get the 6653062250012735*2³⁶⁵. Here, though, you could create the fraction 5*10¹²⁵ / 1 and call .Float64 on it and make sure you get 5e+125 out (you can trust ParseFloat64, you don't need to look at the final field at all).
Similarly, a few lines later, you could create the fraction 836168422905420598437 / 10²³⁴ and call .Float64 on it and make sure you get what ParseFloat says for 836168422905420598437e-234.
Do the same with the strings in the table in src/pkg/strconv/atof_test.go.
If the code can pass both of those sets of cases, then I'll be pretty confident it's right.
Message from unknown
2012-12-14T23:20:10+00:00adonovanurn:md5:aa49fa5adca93d0e19c09cf34d4f4266
Message from adonovan@google.com
2012-12-14T23:22:43+00:00adonovanurn:md5:d27ded4b437515fdf6af8693bca9e3e2
Thanks for the helpful review comments---there were indeed a number of corner cases the tests hadn't touched.
Still one testcase fails, for the exact same reason described in the Java blog post referenced. Suggestions welcome.
Ready for another look.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode35
src/pkg/math/big/rat.go:35: panic("SetFloat requires finite value")
On 2012/12/13 01:52:06, gri wrote:
> SetFloat64
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode35
src/pkg/math/big/rat.go:35: panic("SetFloat requires finite value")
On 2012/12/13 01:52:06, gri wrote:
> on that note, I am wondering if this is a good choice. alternatively, one might
> return nil. as it is, a client will have to check anyway, so why not provide the
> result? also, if the client doesn't pay attention, it will die with a null ptr
> exception when the result is used. about the same.
>
> so: return nil ?
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode37
src/pkg/math/big/rat.go:37: if f == 0.0 {
On 2012/12/13 01:52:06, gri wrote:
> f == 0
>
> seems good enough - we are in Go after all
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode38
src/pkg/math/big/rat.go:38: z.a, z.b = Int{}, *intOne
On 2012/12/13 01:52:06, gri wrote:
> that's not how we do this in this package - you throw away whatever memory is
> hanging of z by doing this
>
> use the appropriate Set function
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode43
src/pkg/math/big/rat.go:43: const SmallestNormal = 2.2250738585072014e-308 // 2**-1022
Per Remy's suggestion, this is gone.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode52
src/pkg/math/big/rat.go:52: mantissa := (1 << 52) | (bits & 0xFFFFFFFFFFFFF)
I tried that but it looked awful: long names everywhere, obscuring the meaning. 11, 52 and 1023 need no explanation.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode53
src/pkg/math/big/rat.go:53: exp := int((bits>>52)&0x7FF) - 1023
Very nice. Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode57
src/pkg/math/big/rat.go:57: z.b = *intOne
On 2012/12/13 01:52:06, gri wrote:
> use Set function so we don't throw away underlying memory
Done.
This package could use some documentation explaining the proper use. I found I had to think quite hard about aliasing to avoid making even more mistakes. That you have to mention a value up to four times in a binary operation z = z.op(z, z) can be a cause for some head-scratching.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode60
src/pkg/math/big/rat.go:60: z.b.abs = z.b.abs.shl(z.b.abs, uint(shift))
On 2012/12/13 01:52:06, gri wrote:
> use set functions
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode69
src/pkg/math/big/rat.go:69: // Preconditions: b is nonzero; a and b have no common factors.
On 2012/12/13 01:52:06, gri wrote:
> s/nonzero/non-zero/
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode82
src/pkg/math/big/rat.go:82: // The result contains mantissa A/B and exponent e.
You're right, it was always finding a value of equal or smaller magnitude, not the nearest.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode97
src/pkg/math/big/rat.go:97: expt := alen - blen
On 2012/12/13 01:52:06, gri wrote:
> s/expt/exp/ please
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode117
src/pkg/math/big/rat.go:117: if expt > 1024 {
Done. (FWIW, that's "return -0.0" in effect.)
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode146
src/pkg/math/big/rat.go:146: mantissa := uint64(q[0] & 0xfffffffffffff) // 52 bits
On 2012/12/13 07:37:38, remyoudompheng wrote:
> This line doesn't compile at all.
> Here Word is 32 bit.
Good catch; I'm testing on 64 bits. Fixed.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode148
src/pkg/math/big/rat.go:148: (uint64((expt+1023)&0x7FF) << 52) | mantissa)
On 2012/12/13 01:52:06, gri wrote:
> one line please
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode165
src/pkg/math/big/rat.go:165: exact = false
On 2012/12/13 01:52:06, gri wrote:
> just return
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat.go#newcode172
src/pkg/math/big/rat.go:172: exact = z2.Cmp(z) == 0
On 2012/12/13 01:52:06, gri wrote:
> I'd do:
>
> if z2.Cmp(z) == 0 {
> exact = true
> }
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat_test.go
File src/pkg/math/big/rat_test.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/big/rat_test.go#newcode508
src/pkg/math/big/rat_test.go:508: // TODO(adonovan): is this ok? Or should I copy the file, or even
On 2012/12/13 14:41:58, rsc wrote:
> You can read the file directly, that's fine. As for using it, what I had
> intended (but not expressed well) was to use the decimal -> binary conversions
> as rat -> binary conversions by building fractions with appropriate
> denominators. For example the file contains
>
> # Table 1: Stress Inputs for Conversion to 53-bit Binary, < 1/2 ULP
> float64 %b 5e+125 6653062250012735p+365
> float64 %b 69e+267 4705683757438170p+841
> float64 %b 999e-026 6798841691080350p-129
>
> In the strconv package that says to try strconv.ParseFloat("5e+125", 64) and
> make sure you get the 6653062250012735*2³⁶⁵. Here, though, you could create the
> fraction 5*10¹²⁵ / 1 and call .Float64 on it and make sure you get 5e+125 out
> (you can trust ParseFloat64, you don't need to look at the final field at all).
>
> Similarly, a few lines later, you could create the fraction
> 836168422905420598437 / 10²³⁴ and call .Float64 on it and make sure you get what
> ParseFloat says for 836168422905420598437e-234.
>
> Do the same with the strings in the table in src/pkg/strconv/atof_test.go.
>
> If the code can pass both of those sets of cases, then I'll be pretty confident
> it's right.
Done.
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go
File src/pkg/math/bits.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go#newcode40
src/pkg/math/bits.go:40: func IsFinite(f float64) bool {
On 2012/12/13 01:52:06, gri wrote:
> why not use IsInf?
This predicate is equivalent to !(IsNaN(f) || IsInf(f,0)) but faster than either arm. I've clarified this in the docstring.
Message from remyoudompheng@gmail.com
2012-12-15T00:17:48+00:00remyoudomphengurn:md5:ed5a4e0b76af0df269ab70ebabf1921c
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/nat.go
File src/pkg/math/big/nat.go (right):
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/nat.go#newcode116
src/pkg/math/big/nat.go:116: return uint64(z[1]<<32 | z[0])
on 32 bits, z[1]<<32 is identically zero.
Can you test your code with GOARCH=386 ?
Also, from a very low-level point of view, adding a private method grows the method table of nat for no particular reason.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode94
src/pkg/math/big/rat.go:94: switch {
It's really not clear why you shift twice.
// Determine A' and B', such A'/B' = A/B * (1<<shift)
// is in the interval [1<<52, 1<<53).
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode105
src/pkg/math/big/rat.go:105: default:
// First we determine α/β where α and β are shifted values
// of A and B such that 1 <= α/β < 2.
// Here we only get 1/2 <= A/B*2^-exp < 2.
// If this is less than 1, decrement exp by 1 to get
// back in interval [1, 2)
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode112
src/pkg/math/big/rat.go:112: // Shift and divide.
// Now we use A'/B' = α/β * 2^52 = A/B * 2^(52-exp).
// A'/B' is in the interval [2^52, 2^53).
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode114
src/pkg/math/big/rat.go:114: var a2, b2 nat
please reuse a2, b2 from above.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode127
src/pkg/math/big/rat.go:127: if mantissa&^(1<<52-1) != 1<<52 {
You want to check that mantissa>>52 == 1.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode139
src/pkg/math/big/rat.go:139: if mantissa == 0x20000000000000 {
1<<53. I really don't want to count the zeroes.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode144
src/pkg/math/big/rat.go:144:
// After rounding, q*2^-52 * 2^exp is a good approximation of A/B
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode151
src/pkg/math/big/rat.go:151:
I would write:
switch {
case exp > 1023:
// infinity
case exp >= -1022:
// finite
case exp < -1022-53:
// zero
default:
// denormal or zero
// q*2^(exp-52) = q*2^(exp+1022)*2^(-1022-52)
shift := uint(-1022-exp)
lostbits := mantissa & (1<<shift - 1)
mantissa >>= shift
switch {
case lostbits == 1<<(shift-1):
// halfway
mantissa &^= 1
case lostbits>>(shift-1) != 0:
// round up
mantissa++
default:
// nothing to do
}
// Now mantissa is in [0, 1<<52]
f = math.Float64frombits(mantissa) // valid even if mantissa == 1<<52
if neg {
f = -f
}
return f
}
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode176
src/pkg/math/big/rat.go:176: // can we tell which is closer?
I'm not sure why it would oscillate.
Denormalized/zero numbers are n * 2^(-1022-52) where n is an integer in [0, 1<<52). The case n==1<<52 is exactly the next float64 so you just have to multiply by 1<<1074 and round to the nearest integer (even if the nearest is 1<<52).
And the closest float64 is well defined.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat_test.go
File src/pkg/math/big/rat_test.go (right):
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat_test.go#newcode645
src/pkg/math/big/rat_test.go:645: // smallest denormal
Please add:
* the exact half of smallest denormal (1p-1075) -> round to zero
* a little more than the exact half of smallest denormal (let's say 1p-1075 + 1p-1100), rounding to 1p-1074
* the exact halfway between smallest normal and largest denormal: 1p-1022 - 1p-1075, rounding to 1p-1022
The decimal representation might be a bit long to write.
Message from rsc@golang.org
2012-12-15T02:49:06+00:00rscurn:md5:3c59f9d0a99f68c4f816944fb108b1bf
Once Remy is happy I'll be happy. :-)
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go
File src/pkg/math/bits.go (right):
https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go#newcode40
src/pkg/math/bits.go:40: func IsFinite(f float64) bool {
To add new API we need more widespread use cases than just one package. Please put this in your new code (unexported) instead of here.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode171
src/pkg/math/big/rat.go:171: if mantissa == 0x10000000000000 {
1<<52
Message from adonovan@google.com
2012-12-15T20:43:46+00:00adonovanurn:md5:8a7da9c7ce1759f932a01474bcff0fdf
Thanks again for the great review comments, and apologies for the lack of
polish. If it wasn't obvious, f.p. code is not my comfort zone and I was
just trying to solicit an extra round of review feedback before checking
out for the weekend.
On 14 December 2012 21:49, <rsc@golang.org> wrote:
> Once Remy is happy I'll be happy. :-)
>
>
>
>
> https://codereview.appspot.**com/6930059/diff/2001/src/pkg/**math/bits.go<https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go>
> File src/pkg/math/bits.go (right):
>
> https://codereview.appspot.**com/6930059/diff/2001/src/pkg/**
> math/bits.go#newcode40<https://codereview.appspot.com/6930059/diff/2001/src/pkg/math/bits.go#newcode40>
> src/pkg/math/bits.go:40: func IsFinite(f float64) bool {
> To add new API we need more widespread use cases than just one package.
> Please put this in your new code (unexported) instead of here.
>
>
> https://codereview.appspot.**com/6930059/diff/11001/src/**
> pkg/math/big/rat.go<https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go>
> File src/pkg/math/big/rat.go (right):
>
> https://codereview.appspot.**com/6930059/diff/11001/src/**
> pkg/math/big/rat.go#newcode171<https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode171>
> src/pkg/math/big/rat.go:171: if mantissa == 0x10000000000000 {
> 1<<52
>
> https://codereview.appspot.**com/6930059/<https://codereview.appspot.com/6930059/>
>
Message from rsc@golang.org
2012-12-17T17:00:33+00:00rscurn:md5:24226e39500bb71eb3a8dd092aa204b8
I am a little worried about the double rounding. I think it would be more clearly correct to tweak the algorithm a little bit.
The state you care about for rounding floating point numbers accurately is:
1) The bits of computed mantissa.
2) The first bit of the remainder fraction.
3) Whether any of the rest of the bits in the remainder are zero.
My suggestion is to generate 54 bits of mantissa, a combination of 1+2.
(That is, the low bit of the quotient is going to be used for rounding and
then thrown away.)
Choose q, r, exp such that
(q + r/b) * 2^(exp-1) = a/b
q in [1<<53, 1<<54)
// Handle denormal loss of precision by moving more into remainder.
haveR := r > 0
if denormal {
n := bits to drop
haveR = haveR || (q & (1<<n-1)) != 0
q >>= n
}
// Round q, dropping the low bit we've been carrying.
if q&1 != 0 && haveR || q&2 == 0 {
q++
}
q >>= 1
f := math.Ldexp(float64(q), exp)
if neg {
f = -f
}
return f
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode94
src/pkg/math/big/rat.go:94: switch {
On 2012/12/15 00:17:48, remyoudompheng wrote:
> It's really not clear why you shift twice.
>
> // Determine A' and B', such A'/B' = A/B * (1<<shift)
> // is in the interval [1<<52, 1<<53).
The first shift makes it possible to use cmp directly.
Otherwise we'd need a custom compare function.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode122
src/pkg/math/big/rat.go:122: // REVIEWERS: what's the recommended memory discipline here?
This is fine for now.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode193
src/pkg/math/big/rat.go:193: // exact is true iff no approximation was involved.
we tend not to use iff in docs.
// If z is exactly representable as a float64, Float64 returns exact=true.
Message from rsc@golang.org
2012-12-17T17:00:54+00:00rscurn:md5:99e292aac94de36b31200dca8e13b468
3) should say ... are nonzero.
Message from unknown
2013-01-25T21:08:42+00:00adonovanurn:md5:2933535f749ddfa9734fd96629b514fd
Message from adonovan@google.com
2013-01-25T21:08:45+00:00adonovanurn:md5:ae6da035bfe7a476702d70c5817ef9f7
Hello remyoudompheng@gmail.com, rsc@golang.org (cc: golang-dev@googlegroups.com),
I'd like you to review this change to
https://code.google.com/p/go/
Message from adonovan@google.com
2013-01-25T21:09:39+00:00adonovanurn:md5:b4b4217c08278afb0c9d3d2115cd5229
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/nat.go
File src/pkg/math/big/nat.go (right):
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/nat.go#newcode116
src/pkg/math/big/nat.go:116: return uint64(z[1]<<32 | z[0])
On 2012/12/15 00:17:48, remyoudompheng wrote:
> on 32 bits, z[1]<<32 is identically zero.
>
> Can you test your code with GOARCH=386 ?
>
> Also, from a very low-level point of view, adding a private method grows the
> method table of nat for no particular reason.
Done.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode105
src/pkg/math/big/rat.go:105: default:
On 2012/12/15 00:17:48, remyoudompheng wrote:
> // First we determine α/β where α and β are shifted values
> // of A and B such that 1 <= α/β < 2.
>
> // Here we only get 1/2 <= A/B*2^-exp < 2.
> // If this is less than 1, decrement exp by 1 to get
> // back in interval [1, 2)
Done.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode139
src/pkg/math/big/rat.go:139: if mantissa == 0x20000000000000 {
On 2012/12/15 00:17:48, remyoudompheng wrote:
> 1<<53. I really don't want to count the zeroes.
Done.
https://codereview.appspot.com/6930059/diff/11001/src/pkg/math/big/rat.go#newcode144
src/pkg/math/big/rat.go:144:
On 2012/12/15 00:17:48, remyoudompheng wrote:
> // After rounding, q*2^-52 * 2^exp is a good approximation of A/B
Done.
Message from unknown
2013-01-25T22:16:50+00:00adonovanurn:md5:ecccfad9fd026aa6a0992f8de6ddb9c7
Message from unknown
2013-01-25T22:19:14+00:00adonovanurn:md5:8f3834579a5c346592daa0546f38cb71
Message from rsc@golang.org
2013-01-25T22:23:50+00:00rscurn:md5:73d24d06c302375a5d61323eb2a0daf4
Looks correct to me!
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode32
src/pkg/math/big/rat.go:32: // If f is not finite, SetFloat simply returns nil.
s/simply //
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode34
src/pkg/math/big/rat.go:34: const expMask = (1 << 11) - 1
drop ( )
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode36
src/pkg/math/big/rat.go:36: mantissa := bits & ((1 << 52) - 1)
drop inner ( )
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode47
src/pkg/math/big/rat.go:47: z.a.SetUint64(mantissa)
Before this, I would suggest
for mantissa&1 == 0 && shift < 0 {
mantissa >>= 1
shift++
}
Then things like 1.0 will give 1/1 instead of 2^52/2^52.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode52
src/pkg/math/big/rat.go:52: // REVIEWERS: what's the correct memory discipline here?
This is fine but you can also let the Int routines worry about it.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode53
src/pkg/math/big/rat.go:53: z.b.abs = z.b.abs.shl(z.b.abs, uint(shift))
z.b.Lsh(&z.b, uint(shift))
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode55
src/pkg/math/big/rat.go:55: z.a.abs = z.a.abs.shl(z.a.abs, uint(-shift))
z.a.Lsh(&z.a, uint(shift))
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode60
src/pkg/math/big/rat.go:60: // isFinite returns whether f represents a finite rational value.
s/returns/reports/
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode127
src/pkg/math/big/rat.go:127: haveRem := len(r) > 0 // m[0]&1 && !haveRem => remainder is exactly half
If you move this up after the mantissa := low64(q) at line 113, then you can change the r = r.add(r, b2) at line 119 to haveRem = true
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode139
src/pkg/math/big/rat.go:139: if mantissa&1 != 0 && haveRem || mantissa&2 != 0 {
Perhaps you meant
if mantissa&1 != 0 && (haveRem || mantissa&2 != 0) {
The condition you've got triggers for mantissa&1 == 0 && mantissa&2 != 0. Luckily, in that case the ++ only touches the low bit, which is about to be shifted away, so it's actually correct, just probably not what you meant.
If you track exactness the bug goes away because you have to split the expression anyway:
exact := !haveRem
if mantissa&1 != 0 {
exact = false
if haveRem || mantissa&2 != 0 {
if mantissa++; mantissa >= 1<<54 {
// Complete rollover 11...1 => 100...0, so shift is safe.
mantissa >>= 1
exp++
}
}
}
mantissa >>= 1
if exp > 1023 {
exact = false
if neg {
f = math.Inf(-1)
}
f = math.Inf(+1)
} else {
f = math.Ldexp(float64(mantissa), exp-53)
}
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode140
src/pkg/math/big/rat.go:140: mantissa++ // may carry into exponent
I know what you mean, but there's no exponent in a mantissa.
// may create 55-bit number
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode142
src/pkg/math/big/rat.go:142: mantissa >>= 1 // discard extra rounding bit. 53 bits left.
// discard rounding bit. Mantissa now scaled by 2^53.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode164
src/pkg/math/big/rat.go:164: // Inefficient!
You might as well figure this out in quotToFloat. See comment above.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go
File src/pkg/math/big/rat_test.go (right):
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode503
src/pkg/math/big/rat_test.go:503: var inputs = []string{
float64inputs
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode695
src/pkg/math/big/rat_test.go:695: if expected != x {
x != expected
The same way you'd write x != nil.
Not the same way xUnit programmers write 0 != f().
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode696
src/pkg/math/big/rat_test.go:696: t.Errorf("string -> Rat -> float64 yielded wrong value; input=%s expected=%g actual=%g error=%g", input, expected, x, (x-expected)/expected)
Use Go syntax to describe values; show x first, like in x != expected.
The general form is:
expression = value, want expected-value
Also, %b will print a float64 using 1p+4 notation, which is usually helpful:
t.Errorf("Rat.SetString(%s).Float64() = %g (%b), want %g (%b); delta=%b", input, x, x, expected, expected, x-expected)
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode712
src/pkg/math/big/rat_test.go:712: t.Error("SetFloat64 returned nil for a finite value", f)
t.Errorf("Rat.SetFloat64(%g) = nil", f)
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode716
src/pkg/math/big/rat_test.go:716: if f != f2 {
f2 != f
But really you can do both here:
if f2 != f || exact != true {
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode717
src/pkg/math/big/rat_test.go:717: t.Error("float64->Rat->float64 roundtrip was lossy", f, f2, (f2-f)/f)
t.Errorf("Rat.SetFloat64(%g).Float64() = %g (%b), %v, want %g (%b), %v; delta=%b", f, f2, f2, exact, f, f, true, f2-f)
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode719
src/pkg/math/big/rat_test.go:719: if !exact {
Can drop (now handled above)
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode730
src/pkg/math/big/rat_test.go:730: t.Errorf("SetFloat64(%g) returned non-nil value: %v", f, r2)
Rat.SetFloat64(%g) = %v, want nil
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode745
src/pkg/math/big/rat_test.go:745: {"1.23456788e-1234", 0.0},
s/.0//
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode746
src/pkg/math/big/rat_test.go:746: {"-1.23456788e-1234", 0.0}, // -0.0, actually
s/0.0/math.Copysign(0, -1)/
and then drop the comment
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode747
src/pkg/math/big/rat_test.go:747: {"1152921504606846975", float64(1<<60 - 1)},
The conversions here should be unnecessary.
1<<60 - 1
-(1<<60 -1)
and so on
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode759
src/pkg/math/big/rat_test.go:759: if s.expected != f {
if f != s.expected
Although here I think you should probably do
if !sameFloat(f, s.expected) || exact != false {
And define
// f1==f2 but treats -0, +0 as distinct.
func sameFloat(f1, f2 float64) {
return math.Float64bits(f1) == math.Float64bits(f2)
}
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode760
src/pkg/math/big/rat_test.go:760: t.Errorf("Rat.Float64() returned incorrect value; literal=%v value=%b expected=%b delta=%g", s.rat, f, s.expected, f-s.expected)
Rat.SetString(%s).Float64() = %g (%b), %v, want %g (%b), %v; delta=%b
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode829
src/pkg/math/big/rat_test.go:829: if r.Cmp(rf0) <= 0 || r.Cmp(rf1) >= 0 {
Maybe you can drop this entirely. The closeness checks will handle this (and arguably give better messages).
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode836
src/pkg/math/big/rat_test.go:836: df0 := new(Rat).Sub(r, rf0) // known > 0
.Abs(new(Rat)) and drop comment
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode837
src/pkg/math/big/rat_test.go:837: df1 := new(Rat).Sub(rf1, r) // known > 0
same
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode839
src/pkg/math/big/rat_test.go:839: t.Errorf("%b (approx. of %v) is not as close as previous float %b", f, r, f0)
"Rat(%v).Float64() = %g (%b), but previous float64 %g (%b) is closer"
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode847
src/pkg/math/big/rat_test.go:847: t.Errorf("%b (approx. of %v) should round halfway to previous (even) float %b ", f, r, f0)
"Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead"
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode861
src/pkg/math/big/rat_test.go:861: 1 / 3,
1.0 / 3 maybe
(1/3 = 0)
Message from unknown
2013-01-28T17:58:37+00:00adonovanurn:md5:d0f71e5610562d5c77757cc2bcb80d52
Message from unknown
2013-01-28T18:02:17+00:00adonovanurn:md5:4b2156fb20349b54773d4d03026af9f3
Message from adonovan@google.com
2013-01-28T18:05:46+00:00adonovanurn:md5:7fc18e46cd896c0960079faa425432b6
PTAL.
Russ, thanks again for the patient and thorough review during which you effectively wrote the entire change (production code and tests) much better than I was evidently doing.
P.S. One discovery I made is that 'apt-get install gnome-genius' gives you a nice infinite-precision calculator: what I wish bc(1) had been.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode32
src/pkg/math/big/rat.go:32: // If f is not finite, SetFloat simply returns nil.
On 2013/01/25 22:23:50, rsc wrote:
> s/simply //
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode34
src/pkg/math/big/rat.go:34: const expMask = (1 << 11) - 1
On 2013/01/25 22:23:50, rsc wrote:
> drop ( )
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode36
src/pkg/math/big/rat.go:36: mantissa := bits & ((1 << 52) - 1)
On 2013/01/25 22:23:50, rsc wrote:
> drop inner ( )
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode47
src/pkg/math/big/rat.go:47: z.a.SetUint64(mantissa)
On 2013/01/25 22:23:50, rsc wrote:
> Before this, I would suggest
>
> for mantissa&1 == 0 && shift < 0 {
> mantissa >>= 1
> shift++
> }
>
> Then things like 1.0 will give 1/1 instead of 2^52/2^52.
Done. (I think you had the sense of < and ++ backwards.)
It's not clear to me that 52 iterations of this loop is saving us much in the common case of 1.0. Is there a good Go definition of ntz(uint64) somewhere? Hacker's Delight has four candidates but none is a one-liner, and I don't think it merits an inline implementation.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode52
src/pkg/math/big/rat.go:52: // REVIEWERS: what's the correct memory discipline here?
On 2013/01/25 22:23:50, rsc wrote:
> This is fine but you can also let the Int routines worry about it.
Right. Sorry for the dumb question---by the time of this review iteration I has already discovered the answer.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode53
src/pkg/math/big/rat.go:53: z.b.abs = z.b.abs.shl(z.b.abs, uint(shift))
On 2013/01/25 22:23:50, rsc wrote:
> z.b.Lsh(&z.b, uint(shift))
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode55
src/pkg/math/big/rat.go:55: z.a.abs = z.a.abs.shl(z.a.abs, uint(-shift))
On 2013/01/25 22:23:50, rsc wrote:
> z.a.Lsh(&z.a, uint(shift))
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode60
src/pkg/math/big/rat.go:60: // isFinite returns whether f represents a finite rational value.
On 2013/01/25 22:23:50, rsc wrote:
> s/returns/reports/
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode127
src/pkg/math/big/rat.go:127: haveRem := len(r) > 0 // m[0]&1 && !haveRem => remainder is exactly half
On 2013/01/25 22:23:50, rsc wrote:
> If you move this up after the mantissa := low64(q) at line 113, then you can
> change the r = r.add(r, b2) at line 119 to haveRem = true
That's better.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode139
src/pkg/math/big/rat.go:139: if mantissa&1 != 0 && haveRem || mantissa&2 != 0 {
On 2013/01/25 22:23:50, rsc wrote:
> Perhaps you meant
> if mantissa&1 != 0 && (haveRem || mantissa&2 != 0) {
>
> The condition you've got triggers for mantissa&1 == 0 && mantissa&2 != 0.
> Luckily, in that case the ++ only touches the low bit, which is about to be
> shifted away, so it's actually correct, just probably not what you meant.
You're absolutely right, I misassociated the expression.
> If you track exactness the bug goes away because you have to split the
> expression anyway:
>
> exact := !haveRem
> if mantissa&1 != 0 {
> exact = false
> if haveRem || mantissa&2 != 0 {
> if mantissa++; mantissa >= 1<<54 {
> // Complete rollover 11...1 => 100...0, so shift is safe.
> mantissa >>= 1
> exp++
> }
> }
> }
> mantissa >>= 1
>
> if exp > 1023 {
> exact = false
> if neg {
> f = math.Inf(-1)
> }
> f = math.Inf(+1)
> } else {
> f = math.Ldexp(float64(mantissa), exp-53)
> }
>
Much better; this saves the expensive exactness check.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go
File src/pkg/math/big/rat_test.go (right):
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode503
src/pkg/math/big/rat_test.go:503: var inputs = []string{
On 2013/01/25 22:23:50, rsc wrote:
> float64inputs
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode695
src/pkg/math/big/rat_test.go:695: if expected != x {
On 2013/01/25 22:23:50, rsc wrote:
> x != expected
>
> The same way you'd write x != nil.
> Not the same way xUnit programmers write 0 != f().
>
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode696
src/pkg/math/big/rat_test.go:696: t.Errorf("string -> Rat -> float64 yielded wrong value; input=%s expected=%g actual=%g error=%g", input, expected, x, (x-expected)/expected)
On 2013/01/25 22:23:50, rsc wrote:
> Use Go syntax to describe values; show x first, like in x != expected.
> The general form is:
> expression = value, want expected-value
>
> Also, %b will print a float64 using 1p+4 notation, which is usually helpful:
>
> t.Errorf("Rat.SetString(%s).Float64() = %g (%b), want %g (%b); delta=%b", input,
> x, x, expected, expected, x-expected)
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode712
src/pkg/math/big/rat_test.go:712: t.Error("SetFloat64 returned nil for a finite value", f)
On 2013/01/25 22:23:50, rsc wrote:
> t.Errorf("Rat.SetFloat64(%g) = nil", f)
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode716
src/pkg/math/big/rat_test.go:716: if f != f2 {
On 2013/01/25 22:23:50, rsc wrote:
> f2 != f
> But really you can do both here:
>
> if f2 != f || exact != true {
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode717
src/pkg/math/big/rat_test.go:717: t.Error("float64->Rat->float64 roundtrip was lossy", f, f2, (f2-f)/f)
On 2013/01/25 22:23:50, rsc wrote:
> t.Errorf("Rat.SetFloat64(%g).Float64() = %g (%b), %v, want %g (%b), %v;
> delta=%b", f, f2, f2, exact, f, f, true, f2-f)
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode719
src/pkg/math/big/rat_test.go:719: if !exact {
On 2013/01/25 22:23:50, rsc wrote:
> Can drop (now handled above)
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode730
src/pkg/math/big/rat_test.go:730: t.Errorf("SetFloat64(%g) returned non-nil value: %v", f, r2)
On 2013/01/25 22:23:50, rsc wrote:
> Rat.SetFloat64(%g) = %v, want nil
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode745
src/pkg/math/big/rat_test.go:745: {"1.23456788e-1234", 0.0},
On 2013/01/25 22:23:50, rsc wrote:
> s/.0//
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode746
src/pkg/math/big/rat_test.go:746: {"-1.23456788e-1234", 0.0}, // -0.0, actually
On 2013/01/25 22:23:50, rsc wrote:
> s/0.0/math.Copysign(0, -1)/
> and then drop the comment
+0.0 and -0.0 are equivalent anyway so this was merely documentation; the test is not comparing bitpatterns or signs.
In any case I realised that all of these testcases (with the exception of "1/3") are all subsumed by the existing float64inputs test as recently augumented.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode747
src/pkg/math/big/rat_test.go:747: {"1152921504606846975", float64(1<<60 - 1)},
On 2013/01/25 22:23:50, rsc wrote:
> The conversions here should be unnecessary.
> 1<<60 - 1
> -(1<<60 -1)
> and so on
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode747
src/pkg/math/big/rat_test.go:747: {"1152921504606846975", float64(1<<60 - 1)},
On 2013/01/25 22:23:50, rsc wrote:
> The conversions here should be unnecessary.
> 1<<60 - 1
> -(1<<60 -1)
> and so on
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode759
src/pkg/math/big/rat_test.go:759: if s.expected != f {
On 2013/01/25 22:23:50, rsc wrote:
> if f != s.expected
>
> Although here I think you should probably do
>
> if !sameFloat(f, s.expected) || exact != false {
>
> And define
>
> // f1==f2 but treats -0, +0 as distinct.
> func sameFloat(f1, f2 float64) {
> return math.Float64bits(f1) == math.Float64bits(f2)
> }
We need to make a special exception for Rat.SetString("-0"): we can't expect Rat to retain the sign, but we do want to ensure that very small negative rationals map to -0.0.
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode760
src/pkg/math/big/rat_test.go:760: t.Errorf("Rat.Float64() returned incorrect value; literal=%v value=%b expected=%b delta=%g", s.rat, f, s.expected, f-s.expected)
On 2013/01/25 22:23:50, rsc wrote:
> Rat.SetString(%s).Float64() = %g (%b), %v, want %g (%b), %v; delta=%b
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode829
src/pkg/math/big/rat_test.go:829: if r.Cmp(rf0) <= 0 || r.Cmp(rf1) >= 0 {
On 2013/01/25 22:23:50, rsc wrote:
> Maybe you can drop this entirely. The closeness checks will handle this (and
> arguably give better messages).
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode836
src/pkg/math/big/rat_test.go:836: df0 := new(Rat).Sub(r, rf0) // known > 0
On 2013/01/25 22:23:50, rsc wrote:
> .Abs(new(Rat)) and drop comment
I think you meant:
df0 := new(Rat).Sub(r, rf0)
df0.Abs(df0)
(This took me a good while to find. I find this calling convention endlessly burdensome despite being aware of its motivation. libgmp suffers from a similar affliction.)
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode837
src/pkg/math/big/rat_test.go:837: df1 := new(Rat).Sub(rf1, r) // known > 0
On 2013/01/25 22:23:50, rsc wrote:
> same
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode839
src/pkg/math/big/rat_test.go:839: t.Errorf("%b (approx. of %v) is not as close as previous float %b", f, r, f0)
On 2013/01/25 22:23:50, rsc wrote:
> "Rat(%v).Float64() = %g (%b), but previous float64 %g (%b) is closer"
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode847
src/pkg/math/big/rat_test.go:847: t.Errorf("%b (approx. of %v) should round halfway to previous (even) float %b ", f, r, f0)
On 2013/01/25 22:23:50, rsc wrote:
> "Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead"
Done.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat_test.go#newcode861
src/pkg/math/big/rat_test.go:861: 1 / 3,
On 2013/01/25 22:23:50, rsc wrote:
> 1.0 / 3 maybe
> (1/3 = 0)
Ouch. That is quite a surprise.
Message from rsc@golang.org
2013-01-28T18:15:07+00:00rscurn:md5:0434a17aba536bd1011da4b7b0f12d37
I think you should decide whether you want the Float64 method to ever return -0. If so, you should test for it. If not, you should test for its absence. I believe reasonable arguments can be made either way, and as long as you define the answer, I'm happy.
It is true that +0 and -0 behave mostly the same in floating point arithmetic, but they are not completely identical. For example: http://play.golang.org/p/eb6pInQoyH. And of course they print differently.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode47
src/pkg/math/big/rat.go:47: z.a.SetUint64(mantissa)
On 2013/01/28 18:05:46, adonovan wrote:
> On 2013/01/25 22:23:50, rsc wrote:
> > Before this, I would suggest
> >
> > for mantissa&1 == 0 && shift < 0 {
> > mantissa >>= 1
> > shift++
> > }
> >
> > Then things like 1.0 will give 1/1 instead of 2^52/2^52.
>
> Done. (I think you had the sense of < and ++ backwards.)
>
> It's not clear to me that 52 iterations of this loop is saving us much in the
> common case of 1.0. Is there a good Go definition of ntz(uint64) somewhere?
> Hacker's Delight has four candidates but none is a one-liner, and I don't think
> it merits an inline implementation.
52 loop iterations is nothing compared to the rest of the stuff going on. I missed the z.norm at the end, though, so maybe it's not actually interesting. Does this function handle 0 correctly now?
Message from adonovan@google.com
2013-01-28T18:52:00+00:00adonovanurn:md5:c41a285bc965c0c0d1c6b532f8eb20cc
On 2013/01/28 18:15:07, rsc wrote:
> I think you should decide whether you want the Float64 method to ever return -0.
> If so, you should test for it.
I think it should return -0 in the case of small but nonzero negative numbers, as indeed it does. All that was lacking was a test case, which I thought was already present but was not. ("-1e-350")
Done.
> It is true that +0 and -0 behave mostly the same in floating point arithmetic,
> but they are not completely identical.
Yes, no argument there.
Message from unknown
2013-01-28T18:52:50+00:00adonovanurn:md5:a63d20733a3ae00bbf9295932824ee4f
Message from adonovan@google.com
2013-01-28T18:54:02+00:00adonovanurn:md5:5d5ea45548c479bb20ae7db2987d3911
I think Float64() should return -0 in the case of small but nonzero negative numbers, as indeed it does. All that was lacking was a test case, which I thought was already present but was not ("-1e-350"). Added now.
> It is true that +0 and -0 behave mostly the same in floating point arithmetic,
> but they are not completely identical.
Yes, no argument there.
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go
File src/pkg/math/big/rat.go (right):
https://codereview.appspot.com/6930059/diff/18001/src/pkg/math/big/rat.go#newcode47
src/pkg/math/big/rat.go:47: z.a.SetUint64(mantissa)
On 2013/01/28 18:15:08, rsc wrote:
> On 2013/01/28 18:05:46, adonovan wrote:
> > On 2013/01/25 22:23:50, rsc wrote:
> > > Before this, I would suggest
> > >
> > > for mantissa&1 == 0 && shift < 0 {
> > > mantissa >>= 1
> > > shift++
> > > }
> > >
> > > Then things like 1.0 will give 1/1 instead of 2^52/2^52.
> >
> > Done. (I think you had the sense of < and ++ backwards.)
> >
> > It's not clear to me that 52 iterations of this loop is saving us much in the
> > common case of 1.0. Is there a good Go definition of ntz(uint64) somewhere?
> > Hacker's Delight has four candidates but none is a one-liner, and I don't
> think
> > it merits an inline implementation.
>
> 52 loop iterations is nothing compared to the rest of the stuff going on. I
> missed the z.norm at the end, though, so maybe it's not actually interesting.
> Does this function handle 0 correctly now?
Yes.
Message from rsc@golang.org
2013-01-28T22:54:23+00:00rscurn:md5:fd5ec03ef5199c8784db436a4b17b3c9
LGTM
Message from unknown
2013-01-28T23:00:12+00:00adonovanurn:md5:951cb60278c63ec4760e859573d75a00
Message from adonovan@google.com
2013-01-28T23:00:27+00:00adonovanurn:md5:f6682d4571b972791135910b49d79191
*** Submitted as https://code.google.com/p/go/source/detail?r=ca5e5de48173 ***
math/big: add Rat.{,Set}Float64 methods for IEEE 754 conversions.
Added tests, using input data from strconv.ParseFloat.
Thanks to rsc for most of the test code.
math/big could use some good package-level documentation.
R=remyoudompheng, rsc
CC=golang-dev
https://codereview.appspot.com/6930059