Fast linear congruential pseudorandom number generators using the Messerschmitt pipelining transformation

The authors show that, despite their recursive nature, linear congruential pseudorandom number generators may be pipelined for high speed operation by means of the Messerschmitt transformation using an iterated version of the system equation. They suggest an appropriate architecture for multiply iterated LCGs pipelined in this way: the hardware overhead required to obtain high speed operation by means of this technique, mainly connected with a more complicated initialisation procedure, is judged to be acceptable. The technique is illustrated by determining the system parameters for multiply iterated versions of the high performance Wichmann-Hill algorithm. Work is in hand to optimise the implementation for VLSI.