2
$\begingroup$

I recall seeing an algorithm in Knuth that builds on two unrelated random number generators to make a better one.

  1. Use generator 1 to populate a table.
  2. Use generator 2 to generate an index and select a value from the table.
  3. Use generator 1 to replace the number that you just used.
  4. Repeat ad nauseum.

Unfortunately my treasured copy of Knuth did not survive my last move. Can anyone tell me who originated this algorithm, and what it is called?

$\endgroup$
4
  • 1
    $\begingroup$ If I properly rememebr, it is the super-random number generator $\endgroup$ Commented Apr 25 at 6:50
  • 4
    $\begingroup$ I do not understand why this was closed. It is a reference request, what other context could possibly be expected? $\endgroup$ Commented Apr 25 at 13:12
  • 5
    $\begingroup$ I feel so powerful. I voted to reopen and it was reopened! $\endgroup$ Commented Apr 27 at 3:27
  • $\begingroup$ @martycohen Thank you. $\endgroup$ Commented Apr 28 at 7:26

1 Answer 1

Reset to default
6
$\begingroup$

What you describe is “Algorithm M (Randomizing by shuffling)” in Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms. The algorithm is attributed to

and

  • George Marsaglia and T. A. Bray, One-line random number generators and their use in combinations, Communications of the ACM, Volume 11, Issue 11 (1968), 757-759, https://doi.org/10.1145/364139.364158.

There is also a variation, called “Algorithm B (Randomizing by shuffling)” which requires only one input sequence. This is attributed to

  • Carter Bays and S. D. Durham, Improving a Poor Random Number Generator, ACM Transactions on Mathematical Software (TOMS), Volume 2, Issue 1 (1976), 59-64, https://doi.org/10.1145/355666.355670.
$\endgroup$
3
  • $\begingroup$ It is indeed MacLaren and Marsaglia. Next question: how did I ever manage to forget? ;-) $\endgroup$ Commented Apr 25 at 7:47
  • 3
    $\begingroup$ @SimonCrase: How did you manage to lose your Knuth books? $\endgroup$ Commented Apr 25 at 8:05
  • 3
    $\begingroup$ We sold our house in the country and moved to a town house. A lot of stuff had to go, sadly. I know have some really cool bars nearby, one with jazz on Sunday afternoons and good Martinis, so it's not all bad... $\endgroup$ Commented Apr 25 at 8:14

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.