FAQ
Hi all,

I was checking the documentation of the math/rand package but I couldnt
find any mention on the generator algorithm.
I checked the source and it looks like a linear congruential generator, is
this correct?

Regards,
Alex

--
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/groups/opt_out.

Search Discussions

  • Anthony Martin at Jul 15, 2013 at 4:29 pm

    athiakos@gmail.com once said:
    I was checking the documentation of the math/rand package but I couldnt
    find any mention on the generator algorithm.
    I checked the source and it looks like a linear congruential generator, is
    this correct?
    No. It's an Additive Lagged Fibonacci Generator (ALFG)
    described by S_n ≡ S_(n-273) + S_(n-607) mod 2^31.

    It's the same code used in Plan 9's rand(2).

    The comments refer to D. P. Mitchell and J. A. Reeds
    (Don Mitchell and Jim Reeds, respectively). Presumably,
    they came up with algorithm while working at Bell Labs.

    I've never found a paper describing it.

    Cheers,
       Anthony

    --
    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/groups/opt_out.
  • Anthony Martin at Jul 15, 2013 at 4:31 pm

    Anthony Martin once said:
    athiakos@gmail.com once said:
    I was checking the documentation of the math/rand package but I couldnt
    find any mention on the generator algorithm.
    I checked the source and it looks like a linear congruential generator, is
    this correct?
    No. It's an Additive Lagged Fibonacci Generator (ALFG)
    described by S_n ≡ S_(n-273) + S_(n-607) mod 2^31.
    Sorry. I meant "mod 2^63". Plan 9's algorithm is mod 2^31.

       Anthony

    --
    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/groups/opt_out.
  • Uli Kunitz at Jul 15, 2013 at 6:20 pm
    Wikipedia has an entry about Lagged Fibonacci Generators. Additive is only
    one variant. The subtractive variant is discussed in Knuth's The Art of
    Computer Programming volume 2 chapter 3.6. As the Wikipedia article he
    mentions problems with birthday spacing tests as well as problem with high
    resolution simulations. Some mitigations are discussed.

    It is definitely not appropriate for any cryptographic use and if it is
    relevant for your simulation work then you will know what to use anyway.
    On Monday, July 15, 2013 6:31:35 PM UTC+2, Anthony Martin wrote:

    Anthony Martin <al...@pbrane.org <javascript:>> once said:
    athi...@gmail.com <javascript:> once said:
    I was checking the documentation of the math/rand package but I
    couldnt
    find any mention on the generator algorithm.
    I checked the source and it looks like a linear congruential
    generator, is
    this correct?
    No. It's an Additive Lagged Fibonacci Generator (ALFG)
    described by S_n ≡ S_(n-273) + S_(n-607) mod 2^31.
    Sorry. I meant "mod 2^63". Plan 9's algorithm is mod 2^31.

    Anthony
    --
    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/groups/opt_out.
  • Athiakos at Jul 15, 2013 at 7:31 pm
    Ok that helps a bit. I dont need crypto quality randoms since I work with
    simulations mostly. But the wiki article doesnt sound good for this algo.
    If I have time I will try the TestU01 battery tests and compare it with
    mersenne.
    Thanks for the help.
    Alex
    On Monday, July 15, 2013 8:20:32 PM UTC+2, Uli Kunitz wrote:

    Wikipedia has an entry about Lagged Fibonacci Generators. Additive is only
    one variant. The subtractive variant is discussed in Knuth's The Art of
    Computer Programming volume 2 chapter 3.6. As the Wikipedia article he
    mentions problems with birthday spacing tests as well as problem with high
    resolution simulations. Some mitigations are discussed.

    It is definitely not appropriate for any cryptographic use and if it is
    relevant for your simulation work then you will know what to use anyway.
    On Monday, July 15, 2013 6:31:35 PM UTC+2, Anthony Martin wrote:

    Anthony Martin <al...@pbrane.org> once said:
    athi...@gmail.com once said:
    I was checking the documentation of the math/rand package but I
    couldnt
    find any mention on the generator algorithm.
    I checked the source and it looks like a linear congruential
    generator, is
    this correct?
    No. It's an Additive Lagged Fibonacci Generator (ALFG)
    described by S_n ≡ S_(n-273) + S_(n-607) mod 2^31.
    Sorry. I meant "mod 2^63". Plan 9's algorithm is mod 2^31.

    Anthony
    --
    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/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJul 15, '13 at 3:09p
activeJul 15, '13 at 7:31p
posts5
users3
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase