When working on some code, I came across a random number generation algorithm (a pseudorandom number generator to be exact, since the numbers aren’t truly random but only designed to “look” like it to the casual observer) called ISAAC. The name stands for “Indirection, Shift, Accumulate, Add, and Count,” which is essentially what it does to a set of state variables, in that sequence.

The algorithm allows sequences of 32-bit numbers to be generated extremely quickly, since the operations it uses are relatively fast on modern processors; in fact, the author, Bob Jenkins, claims it only requires (on average) 18.75 machine processor cycles to generate each 32-bit value.

Even so, the algorithm is designed to be as uniformly distributed as possible.

I decided to test how fast this would be on a relatively modern multiprocessor system. The following is a benchmark on an amd64 machine with 2GB of memory. The benchmark script is available as part of the Math::Random::ISAAC package available via CPAN or its SVN Repository.

Rate | ISAAC PP |
MT | ISAAC XS |
Math::Random | TT800 | Core | |
---|---|---|---|---|---|---|---|

ISAAC::PP | 134/s | — | -54% | -79% | -82% | -90% | -98% |

MT | 292/s | 118% | — | -53% | -61% | -78% | -95% |

ISAAC::XS | 626/s | 367% | 114% | — | -16% | -54% | -90% |

Math::Random | 748/s | 458% | 156% | 19% | — | -45% | -88% |

TT800 | 1350/s | 907% | 362% | 116% | 80% | — | -78% |

Core | 6211/s | 4534% | 2024% | 892% | 730% | 360% | — |

So as we can see, Perl’s built in rand() function is evidently really, really fast; quicker than every other algorithm studied here by a few orders of magnitude. What remains to be seen, then, is whether the quality of random numbers actually generated is any good. Ideally, most random number generators are designed to produce distributions of numbers that are uniformly distributed — that is, every number is equally likely to occur.

Uniform distributions often do not occur in real-life “random” samples – for example, things like height or marks in a class tend to follow more of a normal distribution (or “bell curve”) – the majority of the sample population is near the mean, and it drops off as you go to higher or lower figures. Nonetheless, these types of random numbers are great for uses in computer science — where you want each number to be equally likely, thus ensuring that your sequence is as unpredictable as possible.

In this case, all of the algorithms produce relatively uniform distributions, though the TT800 and Perl rand() core function produce a somewhat jagged distribution. Less interesting distributions are those for ISAAC, Math::Random and the Mersenne Twister.

on 16 June 2009 at 00:59 |civilclubIt is a very good topic.

on 11 November 2009 at 09:43 |ostbeyA more useful graphical representation of the quality of PRNG’s would be to take consecutive pairs of random numbers as the (X,Y) coordinates of a point to plot.

Non-uniform distributions are then easily visible to the naked eye.

It is hard to see any quality differences in the graphs accompanying this article which are essentially big red rectangles.

It is impossible to see with the naked eye whether the fluctuations in these graphs are simply due to randomness or to a shortfall of the associated algorithm.