By Mark Overton
For optimal performance, subcycle RNGs can be shaped many different ways according to application need and processor capabilities
In the first part of this two-part series, Fast, High-Quality, Parallel Random Number Generators , Mark Overton described a new family of fast random number generators based on the subcycles that can be implemented using simple arithmetic. That article provides a detailed description of the concepts behind these generators as well as some examples in C. In this article, the final in this two-part series, he examines the kinds of subcycle generators that exist and describe their respective benefits.
To review, a simple C statement such as x-=rotl(x,21); will produce a surprisingly long cycle of quasi-random numbers with a fixed, known period. rotl is a simple macro that performs a left rotation. The previous expression actually can produce several cycles of different periods, and you usually want to use the longest one. Many other simple expressions also produce such cycles. If the expression is reversible, meaning you can calculate it backward and thus undo it, you can get periods of nearly 232 on 32-bit processors. If an expression is irreversible, you get periods of around 220 or 240 on 32-bit and 64-bit processors respectively, if you select constants carefully.