Anonymous user
Subtractive generator: Difference between revisions
m
added whitespace to the task's preamble.
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 (added whitespace to the task's preamble.) |
||
Line 2:
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><big><math> r_n = r_{(n - i)} - r_{(n - j)} \pmod m </math></big></big>▼
▲ <big><big><math> r_n = r_{(n - i)} - r_{(n - j)} \pmod m </math></big></big>
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.
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>.
Many states generate uniform random integers from <big><big><math> 0 </math></big></big> to <big><big><math> m-1</math></big></big>, but some states are bad. A state, filled with zeros, generates only zeros. If <big><big><math> m </math></big></big> is even, then a state, filled with even numbers, generates only even numbers. More generally, if <big><big><math> f </math></big></big> is a factor of <big><big><math> m</math></big></big>, then a state, filled with multiples of <big><big><math> f</math></big></big>, generates only multiples of <big><big><math> f</math></big></big>.
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.
| |||