ADDITIVE RANDOM NUMBER GENERATORS

USING THE C OR C++ rand() FUNCTION The Structure of Language
index
Back to Deley's Homepage



Additive Random Number Generators


Another type of random number generator not originally discussed in this paper is the additive type. For this type of generator, the Kth output value is the sum of certain previous values, mod M. For example:

SEED[k] = (SEED[k-31] + SEED[k-3]) mod 32

Here the new value is the value we had 31 iterations ago, plus the value we had 3 iterations ago. Note that x31 + x3 + 1 is a polynomial mod 2, and is being used here as a generator. This example is the generator used for the BSD random() random number generator for 32 bit machines. (The 64 bit algorithm uses the generating polynomial x63 + x + 1 which is also a primitive polynomial mod 2).

The period for a additive congruential generator has recently been show to be 2**(e-1) (2**31 - 1) where e is the word size, (see e.g. A.D. Barnard et al., Guaranteeing the period of linear recurring sequences (mod 2**e), IEE Proceedings E140, 243 1993). This is magnitudes greater than the 2**M maximum possible for the linear congruential generators. Also the period of the lowest bit is quite long, compared to the linear congruential generator in which the lowest bit cycles 1,0,1,0,... indefinitely.

Below is some sample C code used to implement the BSD random() random number generator. An array table[31] is initially filled with random numbers using the ANSI C linear congruential random number generator. Random numbers are then generated using the recursion formula:

table[k] = (table[k-31] + table[k-3]) mod 32

Since we are using the array table[] as a circular queue with 31 elements then table[k-31] is just table[k] before it gets replaced with the new value. The recursion formula becomes:

table[k] = table[k] + table[k-3]

Here are the partial results of testing the 32 bit version. Further tests were not performed due to lack of time. So far the generator appears to be comparable to a shuffled linear congruential generator.

DEFINITION:
      Generating polynomial: x^31 + x^3 + 1 (primitive polynomial) Initialize circular queue of 31 elements using ANSI C linear congruential generator.
Recursion formula: a[i] = a[i] + a[i-3]

RATING:
1-D FAILS above 800,000 bpd       (bins per dimension)
2-D FAILS above 3000 bpd
3-D FAILS above 210 bpd
4-D PASSES at 50 bpd (highest tested so far)
5-D not tested
6-D not tested
7-D not tested
8-D not tested

These linear congruential gnererators deserve a more thorough examination than what I have done here. The theory behind these generators is still being developed, and there are still numerous questions about them that mathematicians have yet to answer.



/***
    Code to implement random() & srandom() of BSD Unix. It was taken (though coded somewhat differently) from the Gnu BSD implementation.
***/
#include <stdio.h>
#include <stdlib.h>

#ifdef LONG31 /* x^31 + x^3 + 1 */
#define SIZE 31
#define SIZE1 30
#define P1 3
#define P2 0
#else /* LONG63: x^63 + x + 1 */
#define SIZE 63
#define SIZE1 62
#define P1 1
#define P2 0
#endif

#define LONG_MAX 0x7fffffff

int p1=P1, p2=P2;
long table[SIZE];

/*** return a "random" number in range [0, LONG_MAX] */
long xrand ()
{
int r;

table[p1] = table[p1] + table[p2]; /* add two table elements */
r = (table[p1] >> 1) & LONG_MAX; /* throw least significant bit away */

if (p1 == SIZE1) { /* increment the table indexes */
    p1 = 0;
p2 = p2 + 1;
}
else if (p2 == SIZE1) {
p1 = p1 + 1;
p2 = 0;
}
else {
p1 = p1 + 1;
p2 = p2 + 1;
}

return (r);
}


/***
use a linear congruential type generator to seed the state table & cycle the entire table 10 times
***/
void sxrand (seed)
long seed;
{
int i;

table[0] = seed;
for (i=1; i<SIZE; ++i)
table[i] = (table[i-1] * 1103515145) + 12345; /* lousy */

for (i=0; i<10*SIZE; ++i)
(void) xrand();
}


/*** a small test program ***/
void main ()
{
int i;

sxrand (1); /* BSD default */

for (i=1; i<=40; ++i)
printf ("%ld", xrand() % 10 ); /* least random bits ? */

/* 6714066113586447326208220248220881760069 (cc -DLONG63) */
/* 9418752338157675324663485137890734831064 (cc -DLONG31) */

printf ("\n");
}




ADDENDUM: More on the additive random number generator:



USING THE C OR C++ rand() FUNCTION The Structure of Language
index
Back to Deley's Homepage