Well, I've learned a lot about random numbers this week. Having tried almost a dozen different designs I've come to the conclusion that designing a good generator isn't at all trivial! But it was fun, anyway.
So here's what I came up with. It's incredibly simple, actually, and yet it has some pretty interesting properties:
- Bit width neutral. No matter how many bits in the underlying type, the algorithm is identical and requires no "magic" numbers.
- Invariant period. Regardless of the seed, the period is exactly 4^N, where N is the number of bits in the underlying type. For example, using 32-bit integers the period would be 18,446,744,073,709,551,616, and with a 64-bit type it would be roughly 3.4e+38.
- Good distribution. Over the length of it's period the distribution averages about 82%. Using different cycle lengths the value obtained was generally comparable to other popular algorithms.
- Extremely fast. Each value generated only requires 1 multiply, 4 additions, 4 bit manipulations, and 2 compares. An extra addition is required every 2^N iterations.
- Low overhead. Only 3 words of memory required.
There are, however, some possible disadvantages:
- Due to the simplicity of the operations, there may be some inherent mathematical weaknesses in the context of certain applications.
- Probably not suitable for applications requiring cryptographically secure random numbers (for the above reasons).
If nothing else, though, the algorithm might be a useful component for more complex multiphase generators.
Here is a side-by-side cross-section of a plot of the algorithm compared with the Marsenne twister (using 32768 and 131072 samples, respectively). Can you tell which is which?
Anyway, I would be interested to hear some opinions from the experts, and would like to know if it has any serious flaws?