tholm@uvicctr.UUCP (Terrence W. Holm) (12/10/88)
EFTH MINIX report #61 - December 1988 - rand(3) and lrand(3)
The MINIX rand(3) subroutine uses the common UNIX algorithm.
Unfortunately, this sequence is very non-random in the low order
bits. Machines with only 16 bit int's should use the upper bits,
instead of the lower bits. I have changed the MINIX rand(3) to
return the most significant 15 bits.
I am also including lrand(3). This is for applications requiring
more than the 15 bits from rand(3). Lrand(3) can be used where
lrand48(3) would be used.
----------------------------------------------------------
echo x - rand.3
gres '^X' '' > rand.3 << '/'
XSUBROUTINES
X rand(3) - standard random number generator
X
XINVOCATION
X srand( seed )
X unsigned seed;
X
X int rand()
X
XEXPLANATION
X Rand(3) uses a full period, mixed linear congruential
X generator to return a pseudo-random number in the
X range 0 to 32767 {INT_MAX}. The formula used is:
X
X seed = (1103515245 * seed + 12345) % 2147483648
X
X Srand(3) sets the seed to an initial value, the default
X is 1.
X
XRESULTS
X Rand(3) returns 15 bits from the high order word of seed.
X
XREFERENCES
X lrand(3)
/
echo x - lrand.3
gres '^X' '' > lrand.3 << '/'
XSUBROUTINES
X lrand(3) - lehmer random number generator
X
XINVOCATION
X long seed( lseed )
X long lseed;
X
X long lrand()
X
XEXPLANATION
X Lrand(3) uses a prime modulus multiplicative linear
X congruential generator (PMMLCG) to generate a pseudo-
X random number in the range 1 to 2147483646 {LONG_MAX}-1.
X The generator is much more random than rand(3), especially
X in the low order bits. The formula used is:
X
X seed = (16807 * seed) % 2147483647
X
X Seed(3) sets the seed to an initial value, the default
X is 1.
X
XRESULTS
X Lrand(3) returns the next value of seed.
X
X Seed(3) returns the previous value of seed.
X
XREFERENCES
X rand(3)
/
echo x - rand.c
gres '^X' '' > rand.c << '/'
X/* rand(3)
X *
X * Changed to return high order bits. Terrence W. Holm, Nov. 1988
X */
X
Xstatic long _seed = 1L;
X
Xsrand(x)
X unsigned x;
X {
X _seed = (long) x;
X }
X
Xint rand()
X {
X _seed = 1103515245L * _seed + 12345;
X return( (int) ((_seed >> 16) & 0x7fff) );
X }
/
echo x - lrand.c
gres '^X' '' > lrand.c << '/'
X/* lrand(3)
X *
X * Author: Terrence W. Holm Nov. 1988
X *
X *
X * A prime modulus multiplicative linear congruential
X * generator (PMMLCG), or "Lehmer generator".
X * Implementation directly derived from the article:
X *
X * S. K. Park and K. W. Miller
X * Random Number Generators: Good Ones are Hard to Find
X * CACM vol 31, #10. Oct. 1988. pp 1192-1201.
X *
X *
X * Using the following multiplier and modulus, we obtain a
X * generator which:
X *
X * 1) Has a full period: 1 to 2^31 - 2.
X * 2) Is testably "random" (see the article).
X * 3) Has a known implementation by E. L. Schrage.
X */
X
X
X#define A 16807L /* A "good" multiplier */
X#define M 2147483647L /* Modulus: 2^31 - 1 */
X#define Q 127773L /* M / A */
X#define R 2836L /* M % A */
X
X
Xstatic long _lseed = 1L;
X
X
Xlong seed( lseed )
X long lseed;
X
X {
X long previous_seed = _lseed;
X
X _lseed = lseed;
X
X return( previous_seed );
X }
X
X
Xlong lrand()
X
X {
X _lseed = A * (_lseed % Q) - R * (_lseed / Q);
X
X if ( _lseed < 0 )
X _lseed += M;
X
X return( _lseed );
X }
/
----------------------------------------------------------
Terrence W. Holm
uunet!uw-beaver!uvicctr!tholm
tholm%uvunix.bitnet
tholm%sirius.UVic.ca@relay.ubc.ca