Analysis and synthesis of Ultra-uniform Pseudorandom Number Generators

The Wichmann–Hill algorithm is a high-performance generatorof uniformly distributed pseudorandom numbers, designed foruse on, and portability between, 8-bit of 16-bit machines. Twoanalyses (one number-theoretic, the other probability-theoretic)are presented in order to explain its superb performance. Itis shown that the original Wichmann–Hill configurationcan be regarded as a single linear congruential generator withunrealizably large multiplier and modulus decomposed into threerealizable subgenerators. This provides an obvious insight intothe source of the generator's high quality, but more importantlypermits, for the first time, the application of the extremelystringent Coveyou-MacPherson spectral test—which is passedwith flying colours. The techniques used for analysis have also been applied to designand test a large family of three-component generalized Wichmann–Hill-typegenerators with substantially the same very high performanceas the original. Over one hundred such generators have beenfound. There is no difficulty in extending the design to configurationssuitable for 32-bit machines, with some improvement in the quality.Increasing the number of subgenerators produces a more dramaticenhancement: this is illustrated by means of an example employingfour components.