FAQ
Hi.

Is it really ok to use, as part of the standard library, a random number
generator with no documentation, no studies in the literature, and no info
about algorithm quality in statistical tests like TestU01?


Thanks Manlio

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Konstantin Khomoutov at Mar 11, 2016 at 3:50 pm

    On Fri, 11 Mar 2016 07:33:16 -0800 (PST) Manlio Perillo wrote:

    Is it really ok to use, as part of the standard library, a random
    number generator with no documentation, no studies in the literature,
    and no info about algorithm quality in statistical tests like TestU01?
    Please tone down and be less provocative.
    Your question can be easily rephrased in a way it wouldn't be stepping
    on peoples' toes while in its current form it would easily do.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Manlio Perillo at Mar 11, 2016 at 4:17 pm

    On Fri, Mar 11, 2016 at 4:50 PM, Konstantin Khomoutov wrote:
    On Fri, 11 Mar 2016 07:33:16 -0800 (PST)
    Manlio Perillo wrote:
    Is it really ok to use, as part of the standard library, a random
    number generator with no documentation, no studies in the literature,
    and no info about algorithm quality in statistical tests like TestU01?
    Please tone down and be less provocative.
    Your question can be easily rephrased in a way it wouldn't be stepping
    on peoples' toes while in its current form it would easily do.
    Thanks, I did not notice the tone was provocative, but indeed the
    message was probably too short; I'll rephrase it.

    Recently I found an announce by the V8 team about the new rng in the
    JavaScript implementation.
    I got a bit curious, and I found good documentation about the new
    algorithm (xorshift), some studies in the literature and support in
    the TestU01 tool.

    When I looked at the source code of math/rand, however, I only found
    the authors of the algorithm, but I was unable to find more
    informations.

    Now, in the test package there are some statistical tests, but I'm
    just curious about the reason why a more "known" algorithm was not
    used.
    I can only assume that one of the reason is probably speed and the
    other is that the algorithm was already implemented in Plan9.


    Thanks Manlio

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jesper Louis Andersen at Mar 11, 2016 at 4:09 pm

    On Fri, Mar 11, 2016 at 4:33 PM, Manlio Perillo wrote:

    Is it really ok to use, as part of the standard library, a random number
    generator with no documentation, no studies in the literature, and no info
    about algorithm quality in statistical tests like TestU01?

    I think the Mitchell/Reeds PRNG in math/rand stems from Plan9, and has been
    lifted from the Plan9 C library. You are correct later PRNGs exist.

    Roughly, the problem with an old PRNG can be that its period is too small
    on new hardware. The Wichmann/Hill PRNG in Erlang could go through its full
    period in a little bit less than 24 hours on modern machines, so it was
    changed to an XorShift variant. The API was also extended so it could be
    augmented with new PRNGs and thus remain mostly compatible forward-looking,
    with the default PRNG choice changed as new ones will be adopted. The
    Mersenne Twister is another well-known PRNG with a large period. If you
    also support splitting a seed into multiple seeds, then the period matter
    even more, but I don't think that is the case for the Go PRNG.

    The point of math/rand is to be able to produce a deterministic random
    source so you can something which "looks random", but can be reproduced.
    The large period usually ends up mattering if you use the PRNG as a basis
    for a monte-carlo style simulation, where a small period can produce
    problems (after a while, the same numbers are traversed again).

    The point of crypto/rand is that it is a CSPRNG, which is needed for
    cryptographic security. Its primary property is that you can do no better
    than 50% on predicting the next bit coming out of it, even with a large
    history of existing bits. But these are usually an order of magnitude
    slower than PRNGs, and thus unsuitable for simulations.

    Personally, I always look up the PRNG primitive in order to understand if
    it fits my purpose. I think it is a fine PRNG for running tests in random
    order and so on. I'd probably hesitate using it for long-running
    simulations. If not, rolling your own implmentation of the Source and Rand
    interfaces on top of another kind of random source and PRNG should be
    fairly easy to do. And you should obtain almost seamless integration.

    If you think the PRNG is too weak, you better start computing its period on
    modern hardware and you can also send it through the usual PRNG tests which
    are state-of-the-art. This could demonstrate, backed up with numbers, that
    the default PRNG is too weak in period or randomness.




    --
    J.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Manlio Perillo at Mar 11, 2016 at 4:28 pm

    On Fri, Mar 11, 2016 at 5:09 PM, Jesper Louis Andersen wrote:
    On Fri, Mar 11, 2016 at 4:33 PM, Manlio Perillo wrote:

    Is it really ok to use, as part of the standard library, a random number
    generator with no documentation, no studies in the literature, and no info
    about algorithm quality in statistical tests like TestU01?
    [...]
    The point of math/rand is to be able to produce a deterministic random
    source so you can something which "looks random", but can be reproduced. The
    large period usually ends up mattering if you use the PRNG as a basis for a
    monte-carlo style simulation, where a small period can produce problems
    (after a while, the same numbers are traversed again).

    [...]

    If you think the PRNG is too weak, you better start computing its period on
    modern hardware and you can also send it through the usual PRNG tests which
    are state-of-the-art. This could demonstrate, backed up with numbers, that
    the default PRNG is too weak in period or randomness.
    Well, it is not a problem to know if it is too weak.
    The problem is that some people tend to abuse the standard rng, e.g.:
    http://hackaday.com/2015/12/28/v8-javascript-fixes-horrible-random-number-generator/#what-happened

    without first checking if the rng is good enough for the task, just
    because it is part of the standard library
    (the same problem happened with some "early" versions of the C
    standard library, as reported by Numerical Recipes book).


    Thanks Manlio

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Michael Jones at Mar 12, 2016 at 12:12 pm
    Manila,

    You might take a look at my PGC implementation. It is performant (6.89 ns creation, 7.58 ns value, 25.5 ns value in range) and comes with both standard tests and references to citations.

    https://github.com/MichaelTJones/pcg

    It is what I use in preference to the standard library.

    Michael


    Michael Jones, CEO • michael@wearality.com • +1 650 656-6989
    Wearality Corporation • 289 S. San Antonio Road • Los Altos, CA 94022
    On Mar 11, 2016, at 8:28 AM, Manlio Perillo wrote:

    On Fri, Mar 11, 2016 at 5:09 PM, Jesper Louis Andersen
    wrote:
    On Fri, Mar 11, 2016 at 4:33 PM, Manlio Perillo <manlio.perillo@gmail.com>
    wrote:
    Is it really ok to use, as part of the standard library, a random number
    generator with no documentation, no studies in the literature, and no info
    about algorithm quality in statistical tests like TestU01?
    [...]
    The point of math/rand is to be able to produce a deterministic random
    source so you can something which "looks random", but can be reproduced. The
    large period usually ends up mattering if you use the PRNG as a basis for a
    monte-carlo style simulation, where a small period can produce problems
    (after a while, the same numbers are traversed again).

    [...]

    If you think the PRNG is too weak, you better start computing its period on
    modern hardware and you can also send it through the usual PRNG tests which
    are state-of-the-art. This could demonstrate, backed up with numbers, that
    the default PRNG is too weak in period or randomness.
    Well, it is not a problem to know if it is too weak.
    The problem is that some people tend to abuse the standard rng, e.g.:
    http://hackaday.com/2015/12/28/v8-javascript-fixes-horrible-random-number-generator/#what-happened

    without first checking if the rng is good enough for the task, just
    because it is part of the standard library
    (the same problem happened with some "early" versions of the C
    standard library, as reported by Numerical Recipes book).


    Thanks Manlio

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Michael Jones at Mar 12, 2016 at 12:14 pm
    Manilo, so sorry about what auto-spelling-correction did to your name here. I did type it properly and had to type it and fix it in this email to beat the mangling.


    Michael Jones, CEO • michael@wearality.com • +1 650 656-6989
    Wearality Corporation • 289 S. San Antonio Road • Los Altos, CA 94022
    On Mar 12, 2016, at 4:12 AM, Michael Jones wrote:

    Manila,

    You might take a look at my PGC implementation. It is performant (6.89 ns creation, 7.58 ns value, 25.5 ns value in range) and comes with both standard tests and references to citations.

    https://github.com/MichaelTJones/pcg

    It is what I use in preference to the standard library.

    Michael


    Michael Jones, CEO • michael@wearality.com • +1 650 656-6989
    Wearality Corporation • 289 S. San Antonio Road • Los Altos, CA 94022
    On Mar 11, 2016, at 8:28 AM, Manlio Perillo wrote:

    On Fri, Mar 11, 2016 at 5:09 PM, Jesper Louis Andersen
    wrote:
    On Fri, Mar 11, 2016 at 4:33 PM, Manlio Perillo <manlio.perillo@gmail.com>
    wrote:
    Is it really ok to use, as part of the standard library, a random number
    generator with no documentation, no studies in the literature, and no info
    about algorithm quality in statistical tests like TestU01?
    [...]
    The point of math/rand is to be able to produce a deterministic random
    source so you can something which "looks random", but can be reproduced. The
    large period usually ends up mattering if you use the PRNG as a basis for a
    monte-carlo style simulation, where a small period can produce problems
    (after a while, the same numbers are traversed again).

    [...]

    If you think the PRNG is too weak, you better start computing its period on
    modern hardware and you can also send it through the usual PRNG tests which
    are state-of-the-art. This could demonstrate, backed up with numbers, that
    the default PRNG is too weak in period or randomness.
    Well, it is not a problem to know if it is too weak.
    The problem is that some people tend to abuse the standard rng, e.g.:
    http://hackaday.com/2015/12/28/v8-javascript-fixes-horrible-random-number-generator/#what-happened

    without first checking if the rng is good enough for the task, just
    because it is part of the standard library
    (the same problem happened with some "early" versions of the C
    standard library, as reported by Numerical Recipes book).


    Thanks Manlio

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Manlio Perillo at Mar 12, 2016 at 2:33 pm
    Il giorno sabato 12 marzo 2016 13:14:58 UTC+1, Michael Jones ha scritto:
    Manilo, so sorry about what auto-spelling-correction did to your name
    here. I did type it properly and had to type it and fix it in this email to
    beat the mangling.
    Its not a problem.
    However Manilo is still wrong: my name is Manlio.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Michael Jones at Mar 12, 2016 at 5:20 pm
    Argh! So very sorry. I see this now. I will write it 100 times to make sure
    that I do not forget!
    On Mar 12, 2016 6:33 AM, "Manlio Perillo" wrote:

    Il giorno sabato 12 marzo 2016 13:14:58 UTC+1, Michael Jones ha scritto:
    Manilo, so sorry about what auto-spelling-correction did to your name
    here. I did type it properly and had to type it and fix it in this email to
    beat the mangling.
    Its not a problem.
    However Manilo is still wrong: my name is Manlio.

    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Paul Borman at Mar 12, 2016 at 11:53 pm
    The math/rand package has the following comment:

    *For random numbers suitable for security-sensitive work, see the
    crypto/rand package.*

    I think it is fine that it does not specify the algorithm. If it did, then
    it could not be changed. I believe that as it stands it could be changed
    without breaking the Go 1 compatibility guarantee (depending on how you
    view Seed). If you have specific requirements of your PRNG then you should
    use a package built to meet those requirements.

         -Paul
    On Sat, Mar 12, 2016 at 9:19 AM, Michael Jones wrote:

    Argh! So very sorry. I see this now. I will write it 100 times to make
    sure that I do not forget!
    On Mar 12, 2016 6:33 AM, "Manlio Perillo" wrote:

    Il giorno sabato 12 marzo 2016 13:14:58 UTC+1, Michael Jones ha scritto:
    Manilo, so sorry about what auto-spelling-correction did to your name
    here. I did type it properly and had to type it and fix it in this email to
    beat the mangling.
    Its not a problem.
    However Manilo is still wrong: my name is Manlio.

    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Carl Mastrangelo at Mar 13, 2016 at 5:12 pm
    FWIW, the random numbers are effectively part of the compatibility promise
    unless there are bugs. See https://codereview.appspot.com/95460049 for an
    example where the rand package was sped up significantly, and then
    subsequently reverted. Discuss
    here: https://github.com/golang/go/issues/8013
    On Saturday, March 12, 2016 at 3:53:24 PM UTC-8, Paul Borman wrote:

    The math/rand package has the following comment:

    *For random numbers suitable for security-sensitive work, see the
    crypto/rand package.*

    I think it is fine that it does not specify the algorithm. If it did,
    then it could not be changed. I believe that as it stands it could be
    changed without breaking the Go 1 compatibility guarantee (depending on how
    you view Seed). If you have specific requirements of your PRNG then you
    should use a package built to meet those requirements.

    -Paul

    On Sat, Mar 12, 2016 at 9:19 AM, Michael Jones <m...@wearality.com
    <javascript:>> wrote:
    Argh! So very sorry. I see this now. I will write it 100 times to make
    sure that I do not forget!
    On Mar 12, 2016 6:33 AM, "Manlio Perillo" <manlio....@gmail.com
    <javascript:>> wrote:
    Il giorno sabato 12 marzo 2016 13:14:58 UTC+1, Michael Jones ha scritto:
    Manilo, so sorry about what auto-spelling-correction did to your name
    here. I did type it properly and had to type it and fix it in this email to
    beat the mangling.
    Its not a problem.
    However Manilo is still wrong: my name is Manlio.

    --
    You received this message because you are subscribed to the Google
    Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Manlio Perillo at Mar 13, 2016 at 5:26 pm
    The problem is that, depending on statistical properties of the rng, it may
    not even suitable for simulation work.
    This is fine, since you can use external random number generators.
    However I think that, since the algorithm can not be changed, it should be
    documented in detail.

    Il giorno domenica 13 marzo 2016 00:53:24 UTC+1, Paul Borman ha scritto:
    The math/rand package has the following comment:

    *For random numbers suitable for security-sensitive work, see the
    crypto/rand package.*

    I think it is fine that it does not specify the algorithm. If it did,
    then it could not be changed. I believe that as it stands it could be
    changed without breaking the Go 1 compatibility guarantee (depending on how
    you view Seed). If you have specific requirements of your PRNG then you
    should use a package built to meet those requirements.

    -Paul

    On Sat, Mar 12, 2016 at 9:19 AM, Michael Jones <m...@wearality.com
    <javascript:>> wrote:
    Argh! So very sorry. I see this now. I will write it 100 times to make
    sure that I do not forget!
    On Mar 12, 2016 6:33 AM, "Manlio Perillo" <manlio....@gmail.com
    <javascript:>> wrote:
    Il giorno sabato 12 marzo 2016 13:14:58 UTC+1, Michael Jones ha scritto:
    Manilo, so sorry about what auto-spelling-correction did to your name
    here. I did type it properly and had to type it and fix it in this email to
    beat the mangling.
    Its not a problem.
    However Manilo is still wrong: my name is Manlio.

    --
    You received this message because you are subscribed to the Google
    Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send
    an email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Tapio Raevaara at Mar 12, 2016 at 3:21 am
    I think it's far from ideal that the the behaviour and properties of
    math/rand are completely undocumented, and I hope this will be fixed at
    some point. And maybe it's just me, but naming the package "math/rand"
    instead of just "rand" (or "util/rand" or some such) seems to suggest that
    it might be useful for Monte Carlo simulations and other tasks requiring
    certain statistical properties - but as things stand, I've no way of
    knowing whether that's the case.

    There are, of course, other PRNG implementations outside of the standard
    library, such as this Mersenne Twister implementation:
    https://godoc.org/github.com/seehuhn/mt19937 . Personally I wouldn't mind
    seeing something like MT or WELL in the standard library.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ian Davis at Mar 12, 2016 at 9:34 am

    On Fri, Mar 11, 2016, at 03:33 PM, Manlio Perillo wrote:
    Hi.

    Is it really ok to use, as part of the standard library, a random
    number generator with no documentation, no studies in the literature,
    and no info about algorithm quality in statistical tests like TestU01?
    You might be interested in https://go-review.googlesource.com/#/c/10161/

    Ian

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Manlio Perillo at Mar 12, 2016 at 2:31 pm
    Thanks!

    I will use it, when I will need some random numbers.

    Manlio
    Il giorno sabato 12 marzo 2016 10:34:55 UTC+1, Ian Davis ha scritto:

    On Fri, Mar 11, 2016, at 03:33 PM, Manlio Perillo wrote:

    Hi.

    Is it really ok to use, as part of the standard library, a random number
    generator with no documentation, no studies in the literature, and no info
    about algorithm quality in statistical tests like TestU01?


    You might be interested in https://go-review.googlesource.com/#/c/10161/

    Ian
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Tapio Raevaara at Mar 13, 2016 at 6:09 pm
    New Sources could easily be added to math/rand without breaking Go 1
    compatibility, it's just NewSource() that needs to retain it's current
    implementation (we could have NewPGCSource(), NewMTSource(),
    NewWELLSource() etc.) Although the current API centered around 63-bit ints
    certainly isn't pretty...

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Michael Jones at Mar 13, 2016 at 9:29 pm
    It would be good for discussants to study Melissa O’Neil's PCG paper.

    In supporting PCG’s advances, she does an excellent job of teaching the testing of PRNGs (following L’Ecuyer and Simard, and others), the test results of PRNGs, and most subtly, an analysis of how good an idealized PRNG can be as a function of state size. This last part is quite interesting and her example there was educational to me when I first read and considered it. It was especially important to me because I’d failed to think the matter through and was experiencing my own problems in my software as the result of just this problem.

    Recommended reading: http://www.pcg-random.org/paper.html <http://www.pcg-random.org/paper.html>

    Michael

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedMar 11, '16 at 3:33p
activeMar 13, '16 at 9:29p
posts17
users8
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase