Skip to content

math/rand: remove statistical correlation in ziggurat algorithms #8731

Closed
Closed
math/rand: remove statistical correlation in ziggurat algorithms#8731
Labels
FrozenDueToAgev2An incompatible library change
Milestone
Unplanned

Description

@zephyrtronium
zephyrtronium
opened on Sep 15, 2014
A statistical correlation is present in the algorithms used to generate normally and
exponentially distributed values due to the reuse of random bits for both the
x-coordinate and the segment index. This reuse could be avoided by generating a 63-bit
number, taking the low 32 bits for the x-coordinate, the next 7 or 8 bits for the
segment number, and on the normal distribution, one more bit to determine the sign of
values generated from the tail.

For example: http://play.golang.org/p/xeCjwEFUSs

Activity

  1. ianlancetaylor commented on Sep 15, 2014

    @ianlancetaylor
    ianlancetaylor
    on Sep 15, 2014
    Contributor

    Comment 1:

    Thanks for the report.  Please send patches using the process described at
http://golang.org/doc/contribute.html.  Thanks.

    Labels changed: added repo-main, release-go1.5.

  2. zephyrtronium commented on Sep 16, 2014

    @zephyrtronium
    zephyrtronium
    on Sep 16, 2014
    ContributorAuthor

    Comment 2:

    Alas, a complication: after making these changes and running all.bash, I see that there
are tests to make sure that the outputs of Rand.NormFloat64() and Rand.ExpFloat64() stay
consistent: a contract which this improvement necessarily violates.
  3. zephyrtronium
    added
    new
    repo-main
    release-go1.5
    on Sep 16, 2014
  4. bradfitz
    modified the milestone: Go1.5 on Dec 16, 2014
  5. bradfitz
    removed
    release-go1.5
    new
    on Dec 16, 2014
  6. rsc
    removed
    repo-main
    on Apr 14, 2015

  7. josharian commented on May 2, 2015

    @josharian
    josharian
    on May 2, 2015
    Contributor

    Based on the discussion in #8013, I don't think we can't change this.

    @ianlancetaylor what do you think?

  8. ianlancetaylor commented on May 2, 2015

    @ianlancetaylor
    ianlancetaylor
    on May 2, 2015
    Contributor

    We deliberately postponed the decision in #8013. There were various arguments, but no final decision.

    If the numbers that we get from the generators are statistically correlated, that sounds to me like a bug. I personally would be OK with changing the generated sequence to fix a bug.

    This probably should be discussed on golang-dev, if somebody has a patch.

  9. rsc
    modified the milestones: Unplanned, Go1.5 on Jun 29, 2015
  10. ALTree
    added
    v2An incompatible library change
    on Oct 4, 2017

  11. ianlancetaylor commented on Jan 3, 2018

    @ianlancetaylor
    ianlancetaylor
    on Jan 3, 2018
    Contributor

    For Go 2 I think we are likely to move in the direction of #21835, which seems to be a superior random number generator in any case. I think that is a better place to discuss the future of math/rand. Closing this issue.

  12. ianlancetaylor
    closed this as completedon Jan 3, 2018
  13. golang
    locked and limited conversation to collaborators on Jan 3, 2019
  14. gopherbot
    added
    FrozenDueToAge
    on Jan 3, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    FrozenDueToAgev2An incompatible library change

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions