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:
Xn = (Xn-1 + Xn-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
Xn = (Xn-1 + Xn-p) mod Z
where p is an integer1, or
Xn = (Xn-p + Xn-q + Xn-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
Xn = (Xn-2 + Xn-3 + Xn-5) mod Z
then it would be necessary to come up with 5 different seeds, from X1 to X5 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.