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: document which bits of seed are used #15788

Closed
aarondl opened this issue May 22, 2016 · 8 comments
Closed

math/rand: document which bits of seed are used #15788

aarondl opened this issue May 22, 2016 · 8 comments

Comments

@aarondl
Copy link

@aarondl aarondl commented May 22, 2016

  1. What version of Go are you using (go version)?
    1.6.2 (1.6.0 has the same issue)
  2. What operating system and processor architecture are you using (go env)?
    GOHOSTARCH="amd64"
    GOHOSTOS="linux"
    Ubuntu 14.04.02 Trusty
  3. What did you do?
    If possible, provide a recipe for reproducing the error.
    A complete runnable program is good.
    A link on play.golang.org is best.
    https://play.golang.org/p/JSKCIMotEE
  4. What did you expect to see?
    A different output string, and a different sequence of integers in the array.
  5. What did you see instead?
    The exact same output string, and the exact same sequence of integers in the array.

Basically using a different seed (especially one that's numerically quite different) should probably generate a different random sequence. It's very possible that that's just a limitation of the algorithm and that's life but just in case this is actually a bug I wanted to file it so at least someone with more knowledge than me could confirm it either way.

@kostya-sh
Copy link
Contributor

@kostya-sh kostya-sh commented May 22, 2016

Even though functions in rand take int64 seed parameter the actual implemented algorithm uses only 31 bit of the seed (seed % (2^31-1)). So if two seeds s1 and s2 are different but s1 % (2^31-1) == s2 % (2^31-1) then random sequences produced by rand will be the same for both seeds.

In your example:

474316173889 % 2147483647 = 1869771549
465726239301 % 2147483647 = 1869771549

Probably this should be documented.

@aarondl
Copy link
Author

@aarondl aarondl commented May 22, 2016

Aha, well this information allows me to rewrite my program to fix it. Thanks :) I'll leave this open and let others decide what to do with it, maybe use it to file a documentation bug.

@ianlancetaylor ianlancetaylor changed the title math/rand: Big difference in seed yields exact same random sequences math/rand: document which bits of seed are used May 22, 2016
@ianlancetaylor ianlancetaylor added this to the Go1.7Maybe milestone May 22, 2016
@nullbio
Copy link

@nullbio nullbio commented May 23, 2016

Out of curiosity, why does it take an int64 opposed to an int32 when it only uses 31bits of information?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented May 24, 2016

@BlackBaronsTux The package is written in terms of generating random numbers from a Source interface, which has a method Seed(seed int64). This bug is about the default implementation of Source that you get from calling rand.NewSource.

@jeffallen
Copy link
Contributor

@jeffallen jeffallen commented May 24, 2016

Why is this a doc bug and "let's just change the impl to match what a reasonable person would read in the current docs?"

I'm happy to pick this up as a doc bug, but it seems like it might also be reasonable to collapse the given int64 into an int32 by xor'ing the top 32bits with the bottom 32bits, so that a caller who expects all 64bits to matter will get what they expect. (It also won't change the current behavior of the default seed 1, because 0 ^ 1 == 1.)

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented May 24, 2016

@jeffallen Changing the random number sequences for a given seed is painful for anybody with existing tests that expect a particular sequence. It's a change we would make to fix a clear bug, such as an unexpected lack of randomness, but it's not a change we will make for a problem like this.

@gopherbot
Copy link

@gopherbot gopherbot commented May 24, 2016

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

@gopherbot gopherbot closed this in 3474610 May 24, 2016
@gopherbot
Copy link

@gopherbot gopherbot commented May 26, 2016

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

gopherbot pushed a commit that referenced this issue Jun 26, 2016
Fixes #15788

Change-Id: I5a1fd1e5992f1c16cf8d8437d742bf02e1653b9c
Reviewed-on: https://go-review.googlesource.com/23461
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@golang golang locked and limited conversation to collaborators May 26, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
You can’t perform that action at this time.