Scrambled Multiply-with-Carry Pseudorandom Number Generators

Overview & Synopsis

Multiply-with-carry (MWC) generators are very fast pseudorandom number generators whose quality depends on the choice of a multiplier, and is usually assessed by applying the spectral test to an associated multiplicative congruential generator. We show that the special form of the modulus imposes structural limitations on the lattice structure of every MWC generator, which the generalized MWC generators of Goresky and Klapper mitigate; in our tests, xoring each output with its carry removes them. Since these limitations make the usual worst-case criterion useless, we rank candidates by a weighted geometric mean of their figures of merit, which does not depend on their normalization, and suggest multipliers for generators with 64 to 256 bits of state. Along the way, we correct some errors in the literature. In the end, we propose MWC192X, a 64-bit generator with 192 bits of state that passes all tests we are aware of, and emits an output in half a nanosecond.