Additive

congruential PRNGs work by summing up a set of the previously generated values and then

modulo that sum by a constant. Assuming that the output set of the

PRNG is of the form X

_{1}, X

_{2}, X

_{3}, X

_{4}... in the range 0..Z an example ACPRNG might be of the form:

X_{n} = (X_{n-1} + X_{n-2}) mod Z

This means that to get the current 'random' number, we sum the two previous ones and then find that modulo Z.

Most additive congruential PRNGs are of the form

X_{n} = (X_{n-1} + X_{n-p}) mod Z

where p is an integer^{1}, or

X_{n} = (X_{n-p} + X_{n-q} + X_{n-r}) mod Z

where p, q and r are integers.^{1}

A disadvantage of additive congruential PRNGs is that they will not necessarily output every number in the range 0..Z (but then again, the same is true of genuine random number generators). Another is that they require more than one seed. For example, for the ACPRNG

X_{n} = (X_{n-2} + X_{n-3} + X_{n-5}) mod Z

then it would be necessary to come up with 5 different seeds, from X_{1} to X_{5} before it even gives any output.

It is also true that ACPRNGs are poor choices if Z is a very small number. Here's an example from an ACPRNG which uses the 2 previous values modulo 2 to choose 0 and 1 at 'random':

0

1

1

0

1

1

0

1

1

0

1

1

It carries on like that forever. It's slightly better if we take an ordinary output for a high modulus, and say that if the output is even, take a 0, otherwise take a 1. Using this method with a generator which sums the 2 previous values modulo 2431 (seeds 9173 and 1824) gives:

1

1

0

1

0

1

1

1

1

0

1

0

1

0

0

0

0

1

0

1

1

1

0

This is slightly better, but it's hard to tell with such little output - the period may be something like 24, which is very small but impossible to tell from that small sample. Sometimes even just using your rand() function might be better.

__Footnotes__

^{1} p, q and r are referred to as 'lags' - how far behind the PRNG looks to generate the new value. Hence the alternative name for this PRNG - a lagged generator.

The contents of this writeup are in the public domain.