Prev: Applied Computing 2010: 1st call extension until 25 June 2010
Next: Exchange of the "oracle machine" and the "oracle" in the polynomial-time hierachy
From: Mok-Kong Shen on 12 Jun 2010 05:00

A scheme of using one random number sequence to (pseudo-randomly)
permute the elements of another with the goal to obtain from the latter
sequence a result of better statistical quality is due to M. D.
MacLaren and G. Marsaglia and is described as Algorithm M in Vol. 2 of
Knuth's "The Art of Computer Programming". It consists in establishing
a buffer for the 2nd sequence and, computing from an element of the 1st
sequence a (pseudo-random) pointer to the buffer, outputting the thus
indexed buffer element and replacing it with a newly generated element
of the 2nd sequence. Thus the order of the 2nd sequence gets modified,
which is what the algorithm intends to achieve.

However, IMHO one could evidently make better (more economical) use of
the resources in general situations. For one can employ two buffers, one
for the 1st and one for the 2nd sequence and use each element of each
sequence not only to derive a pointer to index the buffer of the other
sequence but also as the element that is going to enter the buffer
corresponding to the sequence it belongs. That is, the two given
sequences both get randomly shuffled simultaneously (the 1st sequence
by the 2nd and the 2nd by the 1st, i.e. mutually).

M. K. Shen
 | 
Pages: 1
Prev: Applied Computing 2010: 1st call extension until 25 June 2010
Next: Exchange of the "oracle machine" and the "oracle" in the polynomial-time hierachy