Number Theory/32-bit Linear congruential generator
On 32-bit computers, pseudorandom numbers are generated using a linear congruential generator with base b = 40,014 and modulus m = 2,147,483,563 = 231 − 85. As the modulus m = 2,147,483,563 is a prime number, it follows from Fermat's little theorem that for any integer x such that x is not divisible by 2,147,483,563, It also follows that the multiplicative order of x modulo 2,147,483,563 must be either 2,147,483,562 or one of its proper divisors. The base b = 40,014 is a primitive root modulo 2,147,483,563, so this sequence has the full period length of 2,147,483,562.
Modular arithmetic
[edit | edit source]For any prime number p, Fermat's little theorem guarantees that every integer x not divisible by p satisfies the following congruence:
For example, for the prime number p = 13 and base x = 2, we substitute these values into the equation: 212 = 4,096. Fermat's little theorem predicts that this number is congruent to one modulo 13. Indeed, it is: 4,096 = 13 × 315 + 1, so
In a prime modulus, any integer has at most two square roots. The congruence has only the trivial solutions a = ± 1 modulo p. For example, the only square roots of unity modulo 13 are 1 and 12. This is not true for composite moduli; for example, there are four square roots of unity modulo 15: 1, 4, 11, and 14.
Since 2,147,483,563 is a prime number, for any x not congruent to zero modulo 2,147,483,563: Likewise, half of 2,147,483,562 is 1,073,741,781, so either or .
Since 40,014 is a primitive root, it is not a quadratic residue, so . As a result, this value marks the halfway point of the cycle.
Scientific Calculator Function
[edit | edit source]The Texas Instrument calculator TI-30X IIS has a built-in pseudorandom number generator that uses the value of "rand" in the memory storage, accessible by pressing "MEMVAR." To change the value of "rand", store an integer to this variable by pressing "STO", pressing the left arrow button once, and pressing "ENTER." Once an integer is stored to this variable, it will usually stay put, changing when and only when a pseudorandom number is generated. Whenever a pseudorandom number is generated, the "rand" value will change according to the formula: (New Integer) = 40,014 × (Current Integer) modulo 2,147,483,563.
To generate a pseudorandom number, press "PRB" and use "RAND" or "RANDI." Note that, here, "RAND" is in all caps, to distinguish between the integer variable in the memory storage. "RAND" is a pseudorandom decimal number between zero and one, calculated by dividing the new "rand" value by 2,147,483,563. For example, if rand = 500,000,000, then RAND = Texas Instrument calculators round off decimals to the nearest billionth, displaying nine digits beyond the decimal; in this case, this is displayed as 0.232830653.
RANDI is a function that takes two arguments: RANDI(a, b) generates a pseudorandom integer between a and b, inclusive.
Properties
[edit | edit source]- The first term of the cycle is one, and every term after that is calculated by multiplying by 40,014 and taking the remainder modulo 2,147,483,563.
- Second term: 40,014
- Third term: 40,014 × 40,014 = 1,601,120,196
- Fourth term: 1,346,387,765 because
- Fifth term: 439,883,729 because
- The sequence of random numbers repeats every 2,147,483,562 terms.
- The multiplicative inverse of 40,014 is 2,082,061,899 because . The number 2,082,061,899 is the last term of the cycle, after which the cycle starts again from the beginning.
- The last 5 terms of the cycle can be viewed by storing the number 77,872,045 as the seed value, designated as "rand" in the calculator's memory storage, then generating 5 random numbers.
- The negative multiplicative inverse of 40,014 is 65,421,664 because . This marks the halfway point of the cycle.
- Due to the 9-digit precision setting on the calculator, in which all decimal values are displayed rounded to the nearest billionth, the first value of "RAND" after storing 65,421,664 as the seed value is displayed as equaling 1. Actually, this value is , which is so close to one, differing from one by only 4.66 × 10−10, that it rounds to 1.000000000 when the calculator rounds it to nine decimal places.
- The number 65,421,664 is the last term of the first half of the cycle.
- The number 2,147,483,563 − 40,014 = 2,147,443,549 is the first term in the second half of the cycle.
Table of values
[edit | edit source]Note: In this table, m = 2,147,483,563. All RAND values are rounded to nine significant figures. Although the scientific calculator truncates 9-digit decimals ending with zero, the final zeroes will be preserved in this table (i.e., "0.123456000", not "0.123456").
n | RAND | |
---|---|---|
1 | 40,014 | 0.000018633 |
2 | 1,601,120,196 | 0.745579721 |
3 | 1,346,387,765 | 0.626960685 |
4 | 439,883,729 | 0.204836832 |
5 | 732,249,858 | 0.340980425 |
6 | 2,127,568,003 | 0.990726094 |
7 | 1,962,667,596 | 0.913938355 |
8 | 707,287,434 | 0.329356390 |
9 | 1,860,990,862 | 0.866591435 |
10 | 1,695,805,043 | 0.789670791 |
11 | 1,904,850,491 | 0.887015167 |
12 | 53,445,315 | 0.024887415 |
13 | 1,814,689,225 | 0.845030554 |
14 | 112,933,431 | 0.052588729 |
15 | 612,891,482 | 0.285399848 |
16 | 2,124,954,851 | 0.989509251 |
17 | 479,214,492 | 0.223151646 |
18 | 407,948,861 | 0.189965999 |
19 | 643,161,691 | 0.299495513 |
20 | 28,884,682 | 0.013450479 |
21 | 445,508,654 | 0.207456142 |
22 | 322,224,693 | 0.150047571 |
23 | 7,553,450 | 0.003517349 |
24 | 1,596,049,480 | 0.743218485 |
25 | 310,212,663 | 0.144454034 |
26 | 394,503,142 | 0.183704848 |
27 | 1,644,535,938 | 0.765796752 |
28 | 1,269,685,686 | 0.591243494 |
29 | 36,906,150 | 0.017185766 |
30 | 1,441,478,319 | 0.671240676 |
31 | 52,437,849 | 0.024418277 |
32 | 156,648,835 | 0.072945301 |
33 | 1,789,446,856 | 0.833276160 |
34 | 1,529,538,438 | 0.712246866 |
35 | 1,816,996,195 | 0.846104821 |
36 | 82,237,802 | 0.038294962 |
37 | 718,590,712 | 0.334619889 |
38 | 1,031,324,961 | 0.480248128 |
39 | 1,392,842,846 | 0.648593018 |
40 | 1,720,212,868 | 0.801036570 |
41 | 1,454,538,876 | 0.677322472 |
42 | 819,059,838 | 0.381404474 |
43 | 1,113,702,789 | 0.518608295 |
44 | 1,271,983,233 | 0.592313373 |
45 | 1,776,642,162 | 0.827313509 |
46 | 263,600,716 | 0.122748654 |
47 | 1,427,272,131 | 0.664625404 |
48 | 689,175,412 | 0.320922322 |
49 | 828,503,285 | 0.385801922 |
50 | 1,026,683,959 | 0.478086993 |