4 ms·

As pointed out in the comments of the post, this is an LCG[1] PRNG. The Wikipedia article has a good discussion on how to choose parameters, with examples of u

As pointed out in the comments of the post, this is an LCG[1] PRNG. The Wikipedia article has a good discussion on how to choose parameters, with examples of use in the wild from various popular projects over the last many decades. [1]: https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator

Someone 4y ago
And its first reference is to what I consider the definitive reference on the subject, at least for the state of the art in 1968: the Art of Computer Programming. Vol. 2: Seminumerical Algorithms. I also think the only additions that might be needed to that are mentions of newer algorithms that are comparatively simple, but better. The subject itself is pretty well-trodden. Knuth does mention the extremely simple additive random number generator Xn = (Xn-24 + Xn-55) mod m (And says that this can be used directly with floating point values to produce floats in the range [0,1)) It uses 55 words of state (initialized to not all be even), needs only about ten simple instructions to implement (in particular, no multiplications or divisions), has period of at least 2^55-1, and Knuth said it’s very good in practice, isn’t known to be bad, and ends with (in the 1980 second edition of volume 2, with the first edition being from 1968): The only reason it is difficult to recommend sequence (7) wholeheartedly is that there is very little theory to prove that it does or does not have desirable randomness properties; essentially all we know for sure is that the period is very long, and this is not enough” I can’t find anything more recent about this RNG. Has it been forgotten, or was it shown to be bad in some important sense?
- hcs 4y ago
  It's a lagged Fibonacci generator https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator In the third edition (1998) there are a few more notes, most importantly: "Lagged Fibonacci generators have been used successfully in many situations since 1958, so it came as a shock to discover in the 1990s that they actually fail an extremely simple, non-contrived test for randomness" with reference to exercise 3.3.2-31 asking "prove that if we generate 79 consecutive random bits ... starting at a random point in the period, the probability is more than 51% that there are more 1s than 0s". The solution references this paper on the tests: https://arxiv.org/abs/cond-mat/9406054 https://arxiv.org/abs/cond-mat/9406054 There's a recommendation to generate X numbers and only use the first Y an order of magnitude smaller, citing Lüscher's RANLUX, but I don't know how much that holds up either.
  - Someone 4y ago
    Thanks! I focused too much on “additive” as a search term. I even looked at https://en.wikipedia.org/wiki/List_of_random_number_generators https://en.wikipedia.org/wiki/List_of_random_number_generato..., and would have found that better name if I had searched for “Mitchell” or “Moore” there, not “additive”.
    - hcs 4y ago
      FYI if you only have the 2nd edition of volume 2, Knuth provides the full text of the changes from the 2nd to 3rd edition electronically: https://www-cs-faculty.stanford.edu/~knuth/taocp.html https://www-cs-faculty.stanford.edu/~knuth/taocp.html (search for "Errata for Volume 2 (2nd ed.)") Since it's too late to edit the earlier post, this is the specifics around discarding (p571): Lüscher's discarding technique can be used to avoid the bias towards 1s. For example, with lags 55 and 24, no deviation for randomness is observed for random walks of length 1001 when the numbers are generated in batches of 165, if only the first 55 numbers of each batch are used.
- fuglede_ 4y ago
  Fun fact: .NET used Knuth's simple form for their PRNG. Except for some reason they messed up and used Xn-34 instead of Xn-24: https://github.com/dotnet/runtime/issues/23198 https://github.com/dotnet/runtime/issues/23198

Someone 4y ago

And its first reference is to what I consider the definitive reference on the subject, at least for the state of the art in 1968: the Art of Computer Programming. Vol. 2: Seminumerical Algorithms. I also think the only additions that might be needed to that are mentions of newer algorithms that are comparatively simple, but better. The subject itself is pretty well-trodden. Knuth does mention the extremely simple additive random number generator Xn = (Xn-24 + Xn-55) mod m (And says that this can be used directly with floating point values to produce floats in the range [0,1)) It uses 55 words of state (initialized to not all be even), needs only about ten simple instructions to implement (in particular, no multiplications or divisions), has period of at least 2^55-1, and Knuth said it’s very good in practice, isn’t known to be bad, and ends with (in the 1980 second edition of volume 2, with the first edition being from 1968): The only reason it is difficult to recommend sequence (7) wholeheartedly is that there is very little theory to prove that it does or does not have desirable randomness properties; essentially all we know for sure is that the period is very long, and this is not enough” I can’t find anything more recent about this RNG. Has it been forgotten, or was it shown to be bad in some important sense?

hcs 4y ago
It's a lagged Fibonacci generator https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator In the third edition (1998) there are a few more notes, most importantly: "Lagged Fibonacci generators have been used successfully in many situations since 1958, so it came as a shock to discover in the 1990s that they actually fail an extremely simple, non-contrived test for randomness" with reference to exercise 3.3.2-31 asking "prove that if we generate 79 consecutive random bits ... starting at a random point in the period, the probability is more than 51% that there are more 1s than 0s". The solution references this paper on the tests: https://arxiv.org/abs/cond-mat/9406054 https://arxiv.org/abs/cond-mat/9406054 There's a recommendation to generate X numbers and only use the first Y an order of magnitude smaller, citing Lüscher's RANLUX, but I don't know how much that holds up either.
- Someone 4y ago
  Thanks! I focused too much on “additive” as a search term. I even looked at https://en.wikipedia.org/wiki/List_of_random_number_generators https://en.wikipedia.org/wiki/List_of_random_number_generato..., and would have found that better name if I had searched for “Mitchell” or “Moore” there, not “additive”.
  - hcs 4y ago
    FYI if you only have the 2nd edition of volume 2, Knuth provides the full text of the changes from the 2nd to 3rd edition electronically: https://www-cs-faculty.stanford.edu/~knuth/taocp.html https://www-cs-faculty.stanford.edu/~knuth/taocp.html (search for "Errata for Volume 2 (2nd ed.)") Since it's too late to edit the earlier post, this is the specifics around discarding (p571): Lüscher's discarding technique can be used to avoid the bias towards 1s. For example, with lags 55 and 24, no deviation for randomness is observed for random walks of length 1001 when the numbers are generated in batches of 165, if only the first 55 numbers of each batch are used.
fuglede_ 4y ago
Fun fact: .NET used Knuth's simple form for their PRNG. Except for some reason they messed up and used Xn-34 instead of Xn-24: https://github.com/dotnet/runtime/issues/23198 https://github.com/dotnet/runtime/issues/23198