Subtractive generator: Difference between revisions

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