Next: random generators bbs, Previous: random generators mersenne, Up: random generators [Index]
The generators described here were posted by George Marsaglia in a
thread on sci.stat.math and sci.crypt starting on January,
12 1999. The following bindings are exported by the (vicare
crypto randomisations marsaglia) library.
For all the randomness sources, the random-source-seed! function
must be applied to a number maker returning integers representable with
32 bits.
Build and return a new randomness source using the CONG generator.
The state returned by random-source-state-ref is a Scheme vector
of length 2, whose first value is the symbol
random-source-state/marsaglia/cong. The other value is a single
integer representable with 32 bits.
Build and return a new randomness source using the FIB generator.
The state returned by random-source-state-ref is a Scheme vector
of length 3, whose first value is the symbol
random-source-state/marsaglia/fib. The other values are integers
representable with 32 bits.
Build and return a new randomness source using the LFIB4 generator.
The state returned by random-source-state-ref is a Scheme vector
of length 258, whose first value is the symbol
random-source-state/marsaglia/lfib4. The other values are
integers representable with 32 bits.
Build and return a new randomness source using the KISS generator.
The state returned by random-source-state-ref is a Scheme vector
of length 5, whose first value is the symbol
random-source-state/marsaglia/kiss. The other values are
integers representable with 32 bits.
Build and return a new randomness source using the MWC generator.
The state returned by random-source-state-ref is a Scheme vector
of length 3, whose first value is the symbol
random-source-state/marsaglia/mwc. The other values are integers
representable with 32 bits.
Build and return a new randomness source using the SHR3 generator.
The state returned by random-source-state-ref is a Scheme vector
of length 2, whose first value is the symbol
random-source-state/marsaglia/shr3. The other value is an
integer representable with 32 bits.
Build and return a new randomness source using the SWB generator.
The state returned by random-source-state-ref is a Scheme vector
of length 261, whose first value is the symbol
random-source-state/marsaglia/swb. The other values are integers
representable with 32 bits.
Here is the core C language implementation of the generators, as posted by Marsaglia (line wrapping added here, and small bits changed):
#define znew (z = 36969 * (z & 65535) \
+ (z >> 16))
#define wnew (w = 18000 * (w & 65535) \
+ (w >> 16))
#define MWC ((znew << 16) + wnew)
#define SHR3 (jsr ^= (jsr << 17), \
jsr ^= (jsr >> 13), \
jsr ^= (jsr << 5))
#define CONG (jcong = 69069 * jcong + 1234567)
#define FIB ((b = a + b), \
(a = b - a))
#define KISS ((MWC^CONG) + SHR3)
#define LFIB4 (c++, \
t[c] = t[c] \
+ t[(uint8_t)(c + 58)] \
+ t[(uint8_t)(c + 119)] \
+ t[(uint8_t)(c + 178)])
#define SWB (c++, \
bro = (x < y), \
t[c] = (x = t[(uint8_t)(c + 34)]) \
- (y = t[(uint8_t)(c + 19)] \
+ bro))
#define UNI (KISS * 2.328306e-10)
#define VNI (((int32_t) KISS) * 4.656613e-10)
#define UC (uint8_t) /* a cast operation */
/* Use random seeds to reset z, w, jsr, jcong, a, b,
and the table t[256] */
uint32_t z, w, jsr, jcong, a, b, t[256];
uint32_t x=0, y=0, bro;
uint8_t c=0;
What follows is the comment part of the original post by Marsaglia himself, with minor editing for formatting purposes and porting to Scheme (errors in the original text are probably present here, too):
Any one of KISS, MWC, FIB, LFIB4, SWB, SHR3, or CONG can be used in an expression to provide a random 32 bits integer.
The KISS generator (Keep It Simple Stupid) is designed to combine the two multiply–with–carry generators in MWC with the 3–shift register SHR3 and the congruential generator CONG, using addition and exclusive–or. Period about 2^{123}. It is one of my favorite generators.
The MWC generator concatenates two 16 bits multiply–with–carry generators:
x(n) = 36969 * x(n-1) + carry y(n) = 18000 * y(n-1) + carry mod 2^16has period about 2^{60} and seems to pass all tests of randomness. A favorite stand–alone generator—faster than KISS, which contains it.
FIB is the classical Fibonacci sequence:
x(n) = x(n-1) + x(n-2)but taken modulo 2^{32}. Its period is 3 * 2^{31} if one of its two seeds is odd and not 1 mod 8. It has little worth as a RNG by itself, but provides a simple and fast component for use in combination generators.
SHR3 is a 3–shift–register generator with period 2^{32} - 1. It uses:
y(n) = y(n-1) * (I + L^17) * (I + R^13) * (I+L^5)with the y viewed as binary vectors, L the 32 x 32 binary matrix that shifts a vector left 1, and R its transpose. SHR3 seems to pass all tests except those related to the binary rank test, since 32 successive values, as binary vectors, must be linearly independent, while 32 successive truly random 32 bits integers, viewed as binary vectors, will be linearly independent only about 29% of the time.
CONG is a congruential generator with the widely used 69069 multiplier:
x(n) = 69069 * x(n-1) + 1234567it has period 2^{32}. The leading half of its 32 bits seem to pass tests, but bits in the last half are too regular.
LFIB4 is an extension of what I have previously defined as a lagged Fibonacci generator:
x(n) = x(n-r) op x(n-s)with the x in a finite set over which there is a binary operation op, such as +, - on integers modulo 2^{32}, * on odd such integers, exclusive-or(xor) on binary vectors.
Except for those using multiplication, lagged Fibonacci generators fail various tests of randomness, unless the lags are very long. (See SWB below). To see if more than two lags would serve to overcome the problems of 2-lag generators using +, - or xor, I have developed the 4–lag generator LFIB4 using addition:
x(n) = [x(n-256) + x(n-179) + x(n-119) + x(n-55)] mod 2^32its period is 2^{31} * (2^{256} - 1), about 2^{287}, and it seems to pass all tests—in particular, those of the kind for which 2-lag generators using +, -, xor seem to fail. For even more confidence in its suitability, LFIB4 can be combined with KISS, with a resulting period of about 2^{410}, just use:
(let* ((kiss (make-random-source/marsaglia/kiss)) (cong (make-random-source/marsaglia/cong)) (k-integers (random-source-integers-maker kiss)) (c-integers (random-source-integers-maker cong)) (integers (lambda (U M) (mod (+ (k-integers U) (c-integers U)) M)))) ---)in any Scheme expression.
SWB is a subtract–with–borrow generator that I developed to give a simple method for producing extremely long periods:
x(n) = [x(n-222) - x(n-237) - borrow] mod 2^32the
borrowis 0, or set to 1 if computing x(n-1) caused overflow in 32 bits integer arithmetic. This generator has a very long period, 2^{7098} * (2^{480} - 1), about 2^{7578}. It seems to pass all tests of randomness, except for the Birthday Spacings test, which it fails badly, as do all lagged Fibonacci generators using +, - or xor.I would suggest combining SWB with KISS, MWC, SHR3, or CONG. KISS+SWB has period >2^{7700} and is highly recommended. Subtract–with–borrow has the same local behaviour as lagged Fibonacci using +, -, xor—the borrow merely provides a much longer period. SWB fails the birthday spacings test, as do all lagged Fibonacci and other generators that merely combine two previous values by means of +, - or xor. Those failures are for a particular case: m = 512 birthdays in a year of n = 2^{24} days. There are choices of m and n for which lags >1000 will also fail the test. A reasonable precaution is to always combine a 2-lag Fibonacci or SWB generator with another kind of generator, unless the generator uses *, for which a very satisfactory sequence of odd 32 bits integers results.
The classical Fibonacci sequence mod 2^{32} from FIB fails several tests. It is not suitable for use by itself, but is quite suitable for combining with other generators.
The last half of the bits of CONG are too regular, and it fails tests for which those bits play a significant role. CONG+FIB will also have too much regularity in trailing bits, as each does. But keep in mind that it is a rare application for which the trailing bits play a significant role. CONG is one of the most widely used generators of the last 30 years, as it was the system generator for VAX and was incorporated in several popular software packages, all seemingly without complaint.
The generators are seeded as follows:
The seed values are:
jcong = 2524969849
with this seeding it is known that the millionth integer is 1529210297.
The seed values are:
a = 9983651 b = 95746118
with this seeding it is known that the millionth integer is 3519793928.
The seed values are:
jcong = 1017008441 jsr = 3259917390 w = 99545079 z = 2247183469
with this seeding it is known that the millionth integer is 1372460312.
The seed values are stored in a vector of length 256, holding 32
bits representable integers; the index into the vector is set to c
= 0. The seed values of the vector are precomputed, see the source
code of the library.
With this seeding it is known that the millionth integer is 1064612766.
The seed values are:
w = 1046675282 z = 2374144069
with this seeding it is known that the millionth integer is 904977562.
The seed values are:
jsr = 4176875757
with this seeding it is known that the millionth integer is 2642725982.
The seed values are stored in a vector of length 256, holding 32
bits representable integers; the index into the vector is set to c
= 64. The seed values of the vector are precomputed, see the source
code of the library.
With this seeding it is known that the millionth integer is 627749721.
Next: random generators bbs, Previous: random generators mersenne, Up: random generators [Index]