Random number generator (included): Difference between revisions
Random number generator (included) (view source)
Revision as of 00:31, 6 September 2022
, 1 year ago→{{header|ZX Spectrum Basic}}: manual content
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Kinitawowi (talk | contribs) (→{{header|ZX Spectrum Basic}}: manual content) |
||
Line 949:
=={{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.
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}}
|