Comment by Someone | Hacker News Reader

Comment by Someone | Hacker News Reader

Parent Full thread

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?

It's a 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

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.

Thanks! I focused too much on “additive” as a search term. I even looked at 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”.

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 (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.

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

Reply on news.ycombinator.com