Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

math/rand: Float32/Float64 value stream changed since Go 1.2 #8013

Closed
rsc opened this issue May 16, 2014 · 15 comments
Closed

math/rand: Float32/Float64 value stream changed since Go 1.2 #8013

rsc opened this issue May 16, 2014 · 15 comments
Milestone

Comments

@rsc
Copy link
Contributor

rsc commented May 16, 2014

https://golang.org/cl/22730043 fixed a bug in Float32/Float64 to make sure they
never return 1.0.

https://golang.org/cl/69980047 sped up Int31n and Int64n (and therefore Intn,
Float32, and Float64) for powers of two.

The changes have the effect that calling rand with a specific seed and then calling any
of these methods can produce a different number sequence in Go 1.3 than it did in
earlier versions of Go. The Float32/Float64 change is fixing incorrect code, so we have
to keep it. The Int31n/Int64n change is just a performance improvement (but it affects
Intn, Float32, and Float64 output too). 

It's unclear whether we should be trying to keep the output for a fixed seed fixed over
different releases.

If so, we should roll back the performance change and probably make the Float32/Float64
bug fix differently: look for 1.0 and throw it away.

If not, we need to call this out in the release notes. 

I am leaning toward rolling things back but I'm still on the fence.

changeset:   18661:3ed9d5c72102
user:        Jeff R. Allen <jra@nella.org>
date:        Wed Dec 18 15:38:53 2013 -0500
files:       src/pkg/math/rand/example_test.go src/pkg/math/rand/rand.go
src/pkg/math/rand/rand_test.go
description:
math/rand: Float32/64 must only return values in [0,1)

Float32 and Float64 are now both created by taking the ratio
of two integers which are chosen to fit entirely into the
precision of the desired float type. The previous code
could cast a Float64 with more than 23 bits of ".99999"
into a Float32 of 1.0, which is not in [0,1).

Float32 went from 15 to 21 ns/op (but is now correct).

Fixes issue #6721.

R=golang-dev, iant, rsc
CC=golang-dev
https://golang.org/cl/22730043

Committer: Russ Cox <rsc@golang.org>

changeset:   19327:361aac3d88a0
user:        Russ Cox <rsc@golang.org>
date:        Mon Mar 03 20:43:23 2014 -0500
files:       src/pkg/math/rand/rand.go src/pkg/math/rand/rand_test.go
description:
math/rand: speed up Float32, Float64

Actually, speed up Int31n and Int63n by avoiding retry loop.

benchmark           old ns/op    new ns/op    delta
BenchmarkFloat32           32           26  -19.45%
BenchmarkFloat64           46           23  -49.47%

Fixes issue #7267.

LGTM=bradfitz
R=golang-codereviews, bradfitz
CC=golang-codereviews
https://golang.org/cl/69980047
@gopherbot
Copy link

Comment 1 by robpike:

They are called (pseudo) random numbers. Perhaps we should roll back, but also consider
that code that depends on the behavior of a stream of random numbers is poorly designed.
I consider Seed(0) to be useful for checking between runs, but would never expect it to
guarantee the numbers in perpetuity. It's not documented that it can change, but it's
arguably reasonable for it to do so.

@rsc
Copy link
Contributor Author

rsc commented May 16, 2014

Comment 2:

It is maybe worth pointing out that in addition to this changing:
rand.Seed(0)
for i := 0; i < 100; i++ { println(rand.Intn(1<<20))) }
It also affects 
r := rand.New(customSource) 
for i := 0; i < 100; i++ { println(r.Intn(1<<20))) }
So even if you were trying to be good and control the underlying determinism, the change
of algorithm in rand.Rand means you're getting different numbers now.
We can take the weekend at least to think about it.

Status changed to Thinking.

@robpike
Copy link
Contributor

robpike commented May 16, 2014

Comment 3:

I have almost convinced myself it's OK to change this between releases. The determinism
of a stream of random numbers is not a major compatibility point.
If we do let it stand, we need to call the behavior out in the release notes and
document it in the package docs.

@griesemer
Copy link
Contributor

Comment 4:

I am leaning towards documenting that the series of random numbers generated given a
specific seed is not guaranteed to be the same from release to release.
Obviously we want to guarantee that for a given seed and build, we get the same
sequence. But I don't think we want to restrict ourselves from providing a better
generator if one comes along (better statistical behavior, or faster). We also want to
be able to fix serious flaws.

@ianlancetaylor
Copy link
Contributor

Comment 5:

I'm on the fence about the determinism of rand.Seed(0).  I can see arguments either way.
But I'm not really on the fence about rand.New(mySource).  The whole point of the Source
interface is that you get the same sequence of random numbers.  I think we would need a
good reason to change that, like, fixing a bug.  I don't think that performance
improvement is a good enough reason.

Labels changed: added repo-main.

@ianlancetaylor
Copy link
Contributor

Comment 6:

As far as I can tell the glibc rand and random functions have not changed since 1995.

@rsc
Copy link
Contributor Author

rsc commented May 16, 2014

Comment 7:

I investigated more. I was wrong about the Intn/Int31n/Int64n results changing: I
misread the general case as being too conservative when in fact it is exactly right. The
performance improvement there is really just replacing a % with an &. It does not change
the number of values read from the source, nor does it change the output.
Only Float32 and Float64 are changing their results. I suspect we can fix the bug there
without changing the results in practice, since the bug only happened in about 1 in 2^24
or 1 in 2^53 results. But if we do this we should decide that we're committed to not
changing results in general for compatibility (excluding bug fixes).

@rsc
Copy link
Contributor Author

rsc commented May 16, 2014

Comment 8:

I can fix the bug while still preserving every result except the one unlikely buggy
value. Nothing else changes visibly. I propose to do that for Go 1.3. That sidesteps the
issue of whether we could change the results, although we may want to decide and write
something anyway.
I also note that example_test.go says:
// These tests serve as an example but also make sure we don't change
// the output of the random number generator when given a fixed seed.
Sadly, no one paid attention to that: the CL that changed the results just changed the
example.

@rsc
Copy link
Contributor Author

rsc commented May 16, 2014

Comment 9:

CL 95460049 restores the Go 1.2 value streams while still fixing the bug and keeping the
performance improvements. I'll let everyone think over the weekend about what
compatibility guarantees we might want to say in the docs, and I'll mail the CL out
Monday.

@gopherbot
Copy link

Comment 10:

It feels to me performant PRNG and eternally-reproducible PRNG are two separate
concerns. Maybe you shouldn't serve them both with a single implementation.

@robpike
Copy link
Contributor

robpike commented May 16, 2014

Comment 11:

I feel the same. If we need reproducibility over all time, other generators exist. Not
sure we one in the standard library, but it's the right answer for a test that needs a
reproducible stream.

@rsc
Copy link
Contributor Author

rsc commented May 16, 2014

Comment 12:

They are separate concerns but at least so far they are not in conflict, and since we
only provide 1 we might as well avoid gratuitous behavioral differences. Also note Ian's
comment in #5. The Source is the PRNG; the rand.Rand is the algorithms on top.

@gopherbot
Copy link

Comment 13:

CL https://golang.org/cl/95460049 mentions this issue.

@rsc
Copy link
Contributor Author

rsc commented May 19, 2014

Comment 14:

This issue was closed by revision 5aca051.

Status changed to Fixed.

@wadey
Copy link
Contributor

wadey commented May 19, 2014

Comment 15:

Is there no concern that Float64 numbers generated with Int63 results greater than 2^53
will be biased? This is 15% of the result space. Since they can't be accurately
represented by float64, they will be rounded and won't have the same spacing as numbers
below 2^53. I think at least some note should be made that the distribution is not
uniform in the implementation.

This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

6 participants