Subtractive generator: Difference between revisions
Content added Content deleted
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: | 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. |
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. |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
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 <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>. |
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>. |
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. |
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. |