Random number generator (included): Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Kinitawowi (talk | contribs) (→{{header|ZX Spectrum Basic}}: manual content) |
||
Line 949: | Line 949: | ||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
The manual is kind enough to detail how the whole thing works. Nobody is expected to do the maths here, although it has been disassembled online; in short, it's a Park-Miller (or Lehmer) generator. |
|||
The ZX Spectrum uses a Park-Miller (also called a Lehmer) number generator that produces a number between 0 and nearly 1 from a sequence; the RANDOMIZE command can leap to a new entry in the sequence. Multiply the output of RND by 65536 to see the sequence more clearly. The random numbers produced will repeat after 65536 iterations. |
|||
Exercises |
|||
1. Suppose you choose a random number between 1 and 872 and type |
|||
<pre>RANDOMIZE your number</pre> |
|||
Then the next value of RND will be |
|||
<pre>( 75 * ( your number - 1 ) - 1 ) / 65536</pre> |
|||
2. (For mathematicians only.) |
|||
Let <math>p</math> be a (large) prime, and let <math>a</math> be a primitive root modulo <math>p</math>. |
|||
Then if <math>b_i</math> is the residue of <math>a_i</math> modulo <math>p</math> (<math>1 \leq b_i \leq p-1</math>), the sequence |
|||
<math>\frac{b_i-1}{p-1}</math> |
|||
is a cyclical sequence of <math>p-1</math> distinct numbers in the range 0 to 1 (excluding 1). By choosing <math>a</math> suitably, these can be made to look fairly random. |
|||
65537 is a Fermat prime, <math>2^{16}+1</math>. Because the multiplicative group of non-zero residues modulo 65537 has a power of 2 as its order, a residue is a primitive root if and only if it is not a quadratic residue. Use Gauss' law of quadratic reciprocity to show that 75 is a primitive root modulo 65537. |
|||
The ZX Spectrum uses <math>p</math>=65537 and <math>a</math>=75, and stores some <math>b_i-1</math> in memory. RND entails replacing <math>b_i-1</math> in memory by <math>b_{i+1}-1</math>, and yielding the result <math>(b_{i+1}-1)/(p-1)</math>. RANDOMIZE n (with 1 <math>\leq</math> n <math>\leq</math> 65535) makes <math>b_i</math> equal to n+1. |
|||
RND is approximately uniformly distributed over the range 0 to 1. |
|||
{{omit from|6502 Assembly|No RNG}} |
{{omit from|6502 Assembly|No RNG}} |