The Ultimate Macintosh Random-Number Generator

Can you tell the difference?
URLib RANDU
URandomLib RANDU

Random numbers or, at least, pseudo-random numbers are ubiquitous in software, from games to sophisticated Monte Carlo simulations. Programmers are continually reimplementing known algorithms or, much worse, inventing their own.

Faults in a pseudo-random number generator (PRNG) can be subtle and you might have to sit about five feet back from your display to see the one shown above. In each of these 256x256 squares, pixels with odd indices for both row and column were filled in using the individual bits of random integers returned by URandomLib and RANDU, an old PRNG that is no longer used for serious work.

The pattern from URandomLib is quite random. With RANDU, the black pixels tend to form parallel lines slanting up and to the right at about 20 degrees. To some, the two pictures also appear to have different "colors".

URandomLib is the most random, fastest, and most user-friendly library of its kind publically available.

URandomLib 2.0

URandomLib is a random-number library (copyrighted, freeware source) optimized specifically for Macintosh computers. It is an implementation of a well-known PRNG known in the literature as Ultra. Ultra was developed by Marsaglia and coworkers at Florida State Univ. URandomLib was first described in the October, 1998 issue of MacTech magazine. An HTML version of this article is available here. Its primary characteristics are as follows:

Randomness

URandomLib is a compound PRNG comprising a subtract-with-borrow PRNG and a multiplicative congruential PRNG, each of which is an excellent generator in its own right. The compound generator is better than either. It has been very well tested and passes the stringent tests contained in the Diehard suite.

URandomLib is much more random than other PRNGs in two additional ways: First, all bits of the variates it returns are random, not just the MSBs. For proof, see the Coin-flip Test in the demo. Second, the functions returning U(0, 1) and U(-1, 1) retain full float precision regardless of the position of the decimal point. With other PRNGs, such variates lose precision as they approach zero.

Period

URandomLib has an enormous period—approximately 10366. This, of course, refers to the sequence as a whole. If a random variate has only eight bits, there can be only 28 such patterns so there will be many repetitions in a long sequence of bytes.

Ease-of-use

URandomLibx is implemented as a C++ class, automatically instantiated prior to main(). Functionality is described below.

The source is a combination of C++ and assembly. The AltiVec™ coprocessor is not used.

There are four separate implementations. All but the first are PPC-only. The Mach-O libraries require OS X.

--- Caution!
Nearly all of the PRNGs in general use are not threadsafe even if their documentation claims that they are. PRNGs, without exception, maintain a global state and this state may not be duplicated by multiple instantiations without risking correlation between pseudo-random sequences from parallel threads. This is statistically unacceptable! URandomLibMP avoids this problem by utilizing a client/server design with a single source of pseudo-random variates encapsulated within a Critical Region to avoid contention and overlap. There might be a slight overhead penalty (see table below) for this guarantee of randomness.

Speed

URandomLib is very fast because its low-level generator is written in optimized assembly language. [An experimental version in optimized C was slower by nearly a factor of four.] Some indication of what can be expected in this regard is shown in the following table. Timings are averages for 109 calls measured with code (see demo) compiled using CodeWarrior™ 9.2 on a 1.33-GHz G4 running Mac OS 10.3.3. URandomLibMP timings will vary depending upon software design.

Variate Returned PEF/Mach-O Time per Call (nanoseconds)
URandomLib URandomLibMP
bool 10/10 10/9
long 17/22 20/19
float U(0, 1) 71/74 74/75
float Normal(mu, sigma) 297/315 317/331

URandomLib functions

URandomLib supplies 17 functions, in seven categories, as follows:

Initialization

URandomLib is initialized automatically, with random seeds, when a program starts but may be initialized manually as well.

Save/Recall (not available with MP)

Used to save and restore the context of the PRNG so that a sequence of random variates may be repeated exactly

Integer

Returns one of seven unsigned/signed long/int/short formats

Boolean

Returns true or false

Uniform (Real)

Returns single-precision U(0,1) or U(-1,1), or their double-precision equivalents. Note: the single-precision floats retain full precision no matter how small the returned value and can never equal zero.

Normal (Gaussian)

Returns a true (float) Normal(mu, sigma) variate without approximation

Exponential

Returns a true (float) Exponential(lambda) variate without approximation

License

URandomLib is copyrighted freeware. It may be used in any application, including commercial apps, but it may not be sold nor repackaged for sale, in whole or in part, under any circumstances.

Download

You can download the complete package (URandomLib.sitx.hqx, 448 K) from here. [Requires Stuffit Expander™ (free)]

This package includes the four implementations as CodeWarrior™ projects with a demo program to test the compilation. Executables for the demos are included separately.

Still more...

For links to PRNGs in general, check out Luc Devroye's PRNG Page.

To see URandomLib in action, try Regress+.

A more advanced perspective on random numbers is contained in the Compendium of Common Probability Distributions.

Please email any comments, critiques, etc. to Michael P. McLaughlin.

This page last updated on 18 April, 2004.