Anonymous user
Subtractive generator: Difference between revisions
m
used a larger font to make the formulae, italics, super- and subscripts, and symbols easier to read, added other whitespace and highlighting to the task's preamble..
m (→{{header|REXX}}: added/changed comments and whitespace, changed indentations, aligned statements.) |
m (used a larger font to make the formulae, italics, super- and subscripts, and symbols easier to read, added other whitespace and highlighting to the task's preamble..) |
||
Line 1:
{{task|Randomness}}
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▼
▲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.
* <math>r_n = r_{(n - i)} - r_{(n - j)} \pmod m</math>▼
▲<br>The formula is
for some fixed values of <big><big><math> i, </math></big></big> <big><big><math> j, </math></big></big> and <big><big><math> m</math></big></big>, all positive integers.
for some fixed values of <math>i</math>, <math>j</math> and <math>m</math>, all positive integers. Supposing that <math>i > j</math>, then the state of this generator is the list of the previous numbers from <math>r_{n - i}</math> to <math>r_{n - 1}</math>. Many states generate uniform random integers from <math>0</math> to <math>m - 1</math>, but some states are bad. A state, filled with zeros, generates only zeros. If <math>m</math> is even, then a state, filled with even numbers, generates only even numbers. More generally, if <math>f</math> is a factor of <math>m</math>, then a state, filled with multiples of <math>f</math>, generates only multiples of <math>f</math>.▼
Supposing that <big><big><math>i > j</math></big></big>, then the state of this generator is the list of the previous numbers from <big><big><math> r_{n-i} </math></big></big> to <big><big><math> r_{n - 1}</math></big></big>.
▲
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 <math>r_{(n - i)} - r_{(n - j)}</math> is always between <math>-m</math> and <math>m</math>, so a program only needs to add <math>m</math> to negative numbers.▼
All subtractive generators have some weaknesses. The formula correlates <big><big><math> r_n</math></big></big>, <big><big><math> r_{(n-i)} </math></big></big> and <big><big><math> r_{(n-j)}</math></big></big>; these three numbers are not independent, as true random numbers would be.
Anyone who observes <big><big><math> i </math></big></big> consecutive numbers can predict the next numbers, so the generator is not cryptographically secure.
* <math>r_n = r_{(n - 55)} - r_{(n - 24)} \pmod m</math>▼
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 from ''xpat2'' uses▼
▲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><big><math> r_{(n
* <math>r_n = r_{(n - 55)} - r_{(n - 24)} \pmod{10^9}</math>▼
The choice of <big><big><math> i </math></big></big> and <big><big><math> j </math></big></big> affects the period of the generator.
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).▼
A popular choice is <big><big><math> i = 55 </math></big></big> and <big><big><math> j = 24</math></big></big>, so the formula is:
▲The subtractive generator from ''xpat2'' uses:
▲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><big><math> seed </math></big></big> in range <big><big><math> 0 </math></big></big> to <big><big><math> 10^9 - 1</math></big></big>.
# Set <big><big><math> s_0 = seed</math></big></big> and <big><big><math> s_1 = 1</math>.</big></big> The inclusion of <big><big><math> s_1 = 1 </math></big></big> avoids some bad states (like all zeros, or all multiples of 10).
# Compute <big><big><math> s_2, s_3, ..., s_{54} </math></big></big> using the subtractive formula <big><big><math> s_n = s_{(n - 2)} - s_{(n - 1)} \pmod{10^9} </math>
# Reorder these '''55''' values so <big><big><math> r_0 = s_{34}</math></big></big>, <big><big><math> r_1 = s_{13}</math>,</big></big> <big><big><math> r_2 = s_{47}</math></big></big>, ..., <big><big><math> r_n = s_{(34 * (n + 1) \pmod{55})}</math>
#* This is the same order as <big><big><math> s_0 = r_{54}</math></big></big>, <big><big><math> s_1 = r_{33}</math></big></big>, <big><big><math> s_2 = r_{12}</math></big></big>, ..., <big><big><math> s_n = r_{((34 * n) - 1 \pmod{55})}</math>
#* This rearrangement exploits how '''34''' and '''55''' are relatively prime
# Compute the next '''165''' values <big><big><math> r_{55}</math></big></big> to <big><big><math> r_{219}</math></big></big>. Store the last '''55''' values
<br>
This generator yields the sequence <big><big><math> r_{220}</math></big></big>, <big><big><math> r_{221}</math></big></big>, <big><big><math> r_{222} </math></big></big> and so on. For example, if the seed is '''292929''', then the sequence begins with <big><big><math> r_{220} = 467478574</math></big></big>, <big><big><math> r_{221} = 512932792</math></big></big>, <big><big><math> r_{222} = 539453717</math></big></big>. By starting at <big><big><math> r_{220}</math></big></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><big><math> r_n</math></big></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>
=={{header|Ada}}==
| |||