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.

- Function:
**make-random-source/marsaglia/cong** 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.

- Function:
**make-random-source/marsaglia/fib** 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.

- Function:
**make-random-source/marsaglia/lfib4** 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.

- Function:
**make-random-source/marsaglia/kiss** 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.

- Function:
**make-random-source/marsaglia/mwc** 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.

- Function:
**make-random-source/marsaglia/shr3** 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.

- Function:
**make-random-source/marsaglia/swb** 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

32bits 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 about2^{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 is3 * 2^{31}if one of its two seeds is odd and not1 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 period2^{32} - 1. It uses:y(n) = y(n-1) * (I + L^17) * (I + R^13) * (I+L^5)with the

yviewed as binary vectors,Lthe32 x 32binary matrix that shifts a vector left1, andRits transpose. SHR3 seems to pass all tests except those related to the binary rank test, since32successive values, as binary vectors, must be linearly independent, while32successive 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

69069multiplier:x(n) = 69069 * x(n-1) + 1234567it has period

2^{32}. The leading half of its32bits 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

xin a finite set over which there is a binary operationop, such as+,-on integers modulo2^{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+,-orxor, I have developed the4–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), about2^{287}, and it seems to pass all tests—in particular, those of the kind for which2-lag generators using+,-,xorseem to fail. For even more confidence in its suitability, LFIB4 can be combined with KISS, with a resulting period of about2^{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

`borrow`

is0, or set to1if computingx(n-1)caused overflow in 32 bits integer arithmetic. This generator has a very long period,2^{7098} * (2^{480} - 1), about2^{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+,-orxor.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+,-orxor. Those failures are for a particular case:m = 512birthdays in a year ofn = 2^{24}days. There are choices ofmandnfor which lags>1000will also fail the test. A reasonable precaution is to always combine a2-lag Fibonacci or SWB generator with another kind of generator, unless the generator uses*, for which a very satisfactory sequence of odd32bits 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

30years, 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:

- CONG
The seed values are:

jcong = 2524969849

with this seeding it is known that the millionth integer is

*1529210297*.- FIB
The seed values are:

a = 9983651 b = 95746118

with this seeding it is known that the millionth integer is

*3519793928*.- KISS
The seed values are:

jcong = 1017008441 jsr = 3259917390 w = 99545079 z = 2247183469

with this seeding it is known that the millionth integer is

*1372460312*.- LFIB4
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*.- MWC
The seed values are:

w = 1046675282 z = 2374144069

with this seeding it is known that the millionth integer is

*904977562*.- SHR3
The seed values are:

jsr = 4176875757

with this seeding it is known that the millionth integer is

*2642725982*.- SWB
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]