in [Theory]

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 |