37 lines
4.7 KiB
Plaintext
37 lines
4.7 KiB
Plaintext
A ''subtractive generator'' calculates a sequence of [[random number generator|random numbers]], where each number is congruent to the subtraction of two previous numbers from the sequence. <br>
|
|
The formula is
|
|
|
|
* <big><math>r_n = r_{(n - i)} - r_{(n - j)} \pmod m</math></big>
|
|
|
|
for some fixed values of <big><math>i</math></big>, <big><math>j</math></big> and <big><math>m</math></big>, all positive integers. Supposing that <big><math>i > j</math></big>, then the state of this generator is the list of the previous numbers from <big><math>r_{n - i}</math></big> to <big><math>r_{n - 1}</math></big>. Many states generate uniform random integers from <big><math>0</math></big> to <big><math>m - 1</math></big>, but some states are bad. A state, filled with zeros, generates only zeros. If <big><math>m</math></big> is even, then a state, filled with even numbers, generates only even numbers. More generally, if <big><math>f</math></big> is a factor of <big><math>m</math></big>, then a state, filled with multiples of <big><math>f</math></big>, generates only multiples of <big><math>f</math></big>.
|
|
|
|
All subtractive generators have some weaknesses. The formula correlates <big><math>r_n</math></big>, <big><math>r_{(n - i)}</math></big> and <big><math>r_{(n - j)}</math></big>; these three numbers are not independent, as true random numbers would be. Anyone who observes <big><math>i</math></big> consecutive numbers can predict the next numbers, so the generator is not cryptographically secure. The authors of ''Freeciv'' ([http://svn.gna.org/viewcvs/freeciv/trunk/utility/rand.c?view=markup utility/rand.c]) and ''xpat2'' (src/testit2.c) knew another problem: the low bits are less random than the high bits.
|
|
|
|
The subtractive generator has a better reputation than the [[linear congruential generator]], perhaps because it holds more state. A subtractive generator might never multiply numbers: this helps where multiplication is slow. A subtractive generator might also avoid division: the value of <big><math>r_{(n - i)} - r_{(n - j)}</math></big> is always between <big><math>-m</math></big> and <big><math>m</math></big>, so a program only needs to add <big><math>m</math></big> to negative numbers.
|
|
|
|
The choice of <big><math>i</math></big> and <big><math>j</math></big> affects the period of the generator. A popular choice is <big><math>i = 55</math></big> and <big><math>j = 24</math></big>, so the formula is
|
|
|
|
* <big><math>r_n = r_{(n - 55)} - r_{(n - 24)} \pmod m</math></big>
|
|
|
|
The subtractive generator from ''xpat2'' uses
|
|
|
|
* <big><math>r_n = r_{(n - 55)} - r_{(n - 24)} \pmod{10^9}</math></big>
|
|
|
|
The implementation is by J. Bentley and comes from program_tools/universal.c of [ftp://dimacs.rutgers.edu/pub/netflow/ the DIMACS (netflow) archive] at Rutgers University. It credits Knuth, [[wp:The Art of Computer Programming|''TAOCP'']], Volume 2, Section 3.2.2 (Algorithm A).
|
|
|
|
Bentley uses this clever algorithm to seed the generator.
|
|
|
|
# Start with a single <big><math>seed</math></big> in range <big><math>0</math></big> to <big><math>10^9 - 1</math></big>.
|
|
# Set <big><math>s_0 = seed</math></big> and <big><math>s_1 = 1</math></big>. The inclusion of <big><math>s_1 = 1</math></big> avoids some bad states (like all zeros, or all multiples of 10).
|
|
# Compute <big><math>s_2, s_3, ..., s_{54}</math></big> using the subtractive formula <big><math>s_n = s_{(n - 2)} - s_{(n - 1)} \pmod{10^9}</math></big>.
|
|
# Reorder these 55 values so <big><math>r_0 = s_{34}</math></big>, <big><math>r_1 = s_{13}</math></big>, <big><math>r_2 = s_{47}</math></big>, ..., <big><math>r_n = s_{(34 * (n + 1) \pmod{55})}</math></big>.
|
|
#* This is the same order as <big><math>s_0 = r_{54}</math></big>, <big><math>s_1 = r_{33}</math></big>, <big><math>s_2 = r_{12}</math></big>, ..., <big><math>s_n = r_{((34 * n) - 1 \pmod{55})}</math></big>.
|
|
#* This rearrangement exploits how 34 and 55 are relatively prime.
|
|
# Compute the next 165 values <big><math>r_{55}</math></big> to <big><math>r_{219}</math></big>. Store the last 55 values.
|
|
|
|
This generator yields the sequence <big><math>r_{220}</math></big>, <big><math>r_{221}</math></big>, <big><math>r_{222}</math></big> and so on. For example, if the seed is 292929, then the sequence begins with <big><math>r_{220} = 467478574</math></big>, <big><math>r_{221} = 512932792</math></big>, <big><math>r_{222} = 539453717</math></big>. By starting at <big><math>r_{220}</math></big>, this generator avoids a bias from the first numbers of the sequence. This generator must store the last 55 numbers of the sequence, so to compute the next <big><math>r_n</math></big>. Any array or list would work; a [[ring buffer]] is ideal but not necessary.
|
|
|
|
Implement a subtractive generator that replicates the sequences from ''xpat2''.
|
|
<br><br>
|
|
|