3 ms·
It's a lagged Fibonacci generator https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator In the thi
by 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 agoThanks! 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 agoFYI 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.