Date   : Thu, 11 Apr 1985 13:15:00 PST
From   : Eldridge.es@XEROX.ARPA
Subject: Re: random numbers

This message describes several "linear congruential" random number
generators.

A characteristic of the linear congruential method is that the maximum
period is determined by the precision of arithmetic used.  For example,
using 16-bit binary arithmetic, the maximum possible period is 65,535.
To make the period reasonably large, 32-bit binary arithmetic should be
used.  The selection of the multiplier and constant also affect the
period and distribution of the random numbers. (For more on this refer
to Knuth, Semi-Numerical Algorithms)

Here is the random number generator from a Unix system.  It runs on a
VAX which has 32 bit words.

/* @(#)rand.c  4.1 (Berkeley) 12/21/80 */
static long    randx = 1;

srand(x)
unsigned x;
{
       randx = x;
}

rand()
{
       return((randx = randx * 1103515245 + 12345) & 0x7fffffff);
}



If you have real arithmetic available, you might want to try the
following random number generator.  It generates a real in the range 0 <
n < 1.  This one has a period of 1 million.  It comes from the HP-67
library.

NewSeed := Frac(9821. * Seed + 0.211327)

Caution: be sure to avoid a starting seed equal to (1. - 0.211327)/9821.
That seed will produce a result of zero.  This formula assumes that the
precision of the arithmetic is ten decimal digits or better.


Most random number generators produce uniformly distributed numbers.
Sometimes it is desirable to have normally (Gaussian) distributed
numbers.  The following formula can be used to convert uniformly
distributed numbers into normally distributed numbers with a given mean
and standard deviation.


T = sqrt(-2*ln(rand1))*sin(360*rand2)

G = StdDev*T + Mean

where

rand1 : random number in the range 0 < n < 1
rand2 : another random number in the range 0 < n < 1
StdDev : standard deviation of desired distribution
Mean : mean of desired distribution

Reference
Knuth, Semi-Numerical Algorithms p. 104

The only drawback is that transcendental functions must be evaluated.
This can be speeded up at the expense of memory by the use of table
look-up.

George