URandomLib
Volume Number: 14
Issue Number: 10
Column Tag: Tools Of The Trade
URandomLib: The Ultimate Macintosh
Random-Number Generator
by Michael McLaughlin, McLean, VA
Include this class in your projects and never have to worry
about random numbers again
The Value of Nothing
Try to think of nothing. It's difficult. Sensory data alone tend to bias our thoughts and
the brain tries to perceive patterns in this stream even when there is nothing there.
Random numbers are the software analogue of nothing, the sound of no hands clapping.
They are used primarily as input, either by themselves or in conjunction with other
data.
The unique value of random input is that it is completely neutral. Patterns of any kind,
discernable in the output, could not have come from such input and must, instead, be
attributed to whatever additional systems are present. Typically, it is the behavior of
these systems that is of interest and a random input stream is a way of exercising the
software without telling it what to do.
Small wonder, then, that the generation of "random" numbers has always been, and
continues to be, a perennial topic in computer science. Applications range from the
trivial (e.g., games) to the deadly serious (e.g., Monte Carlo simulations of nuclear
reactors). In the latter case, the quality of the random numbers is very important.
This is one time when "rolling-your-own" is definitely not recommended.
Of course, any algorithm purporting to produce random numbers cannot really do so.
At best, the output will be pseudo-random, meaning only that there are no detectable
patterns in it. Tests for such patterns are an active area of research and can be quite
sophisticated. Our goals here are more modest and we shall focus on creating random
numbers, not testing them.
The utility class, URandomLib, that is described in this article is a complete
pseudo-random number generator (PRNG), implemented as a library. URandomLib
makes the creation of random numbers about as trivial as one could wish, while
assuring unsurpassed quality and execution speed.
The speed comes from the fact the low-level function responsible for the random
stream is coded in optimized assembly language. The quality of the output comes from
having a world-class algorithm which produces numbers that are very random.
How Random Are They?
They are so random that you can use any of the individual bits just as you would the
entire output value of ordinary generators. This is unusual and most PRNGs come with
dire warnings against breaking up a random binary word into separate pieces. As we
shall see, URandomLib does so with impunity and even uses this as an additional
mechanism to decrease execution time.
All PRNGs generate new random numbers using the previous one(s) as input, but
there are many different algorithms. The most common, by far, are the multiplicative
congruential generators. With these algorithms, each random integer, X, comes from
the formula
X[i+1] = (a*X[i]) % m
where a and m are (unsigned long) constants.
However, just any old a and m will not do. If you simply make them up, your random
numbers will not be very random.
Randomness is one of the two necessary features of any PRNG. The other is a long
period, the length of the random sequence before the numbers start repeating
themselves. Speed is a third feature, not absolutely necessary but highly desirable.
When you pick inferior values for a and m, you can get bad results. Once upon a time,
there was a famous PRNG known as RANDU. Almost everybody used it. RANDU was a
multiplicative congruential generator with a = 65539 and m = 2147483648. The
value of m (= 0x80000000) was chosen because it makes the modulo operation very
easy, especially in assembly language where you can do whatever you like. The value of
a (= 0x10003) was reportedly chosen because its binary representation has only
three 1-bits, making multiplication unusually fast. Today, RANDU is used only as an
example of how not to construct a PRNG. We shall see why later, when we compare it
to URandomLib.
The generator algorithm in URandomLib is known as "Ultra." It is a strenuously tested
compound generator. In this case, the output from the first generator is XORed with the
output of an independent generator which, all by itself, is quite a good PRNG.
The first PRNG in Ultra is a subtract-with-borrow (SWB) generator which works as
follows: [See Marsaglia and Zaman, in Further Reading, for details.]
Let b = 232 and m = b37 - b24 - 1, a prime number. If X[0] ... X[36] are 37
integers in the closed interval [0, b-1], not all zero or b-1, and c the carry (or
borrow) bit from the previous operation, then the sequence constructed using the
recursion
X[n] = (X[n-24] - X[n-37] - c) % b
has a period of m-1, about 10356. There is a lot more theory involved, as well as