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 = 2³¹ − 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, $x^{2,147,483,562}\equiv 1{\pmod {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

For any prime number p, Fermat's little theorem guarantees that every integer x not divisible by p satisfies the following congruence: $x^{p-1}\equiv 1{\pmod {p}}.$

For example, for the prime number p = 13 and base x = 2, we substitute these values into the equation: 2¹² = 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 $2^{12}\equiv 1{\pmod {13}}.$

In a prime modulus, any integer has at most two square roots. The congruence $a^{2}\equiv 1{\pmod {p}}.$ 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: $x^{2,147,483,562}\equiv 1{\pmod {2,147,483,563}}.$ Likewise, half of 2,147,483,562 is 1,073,741,781, so either $x^{1,073,741,781}\equiv 1{\pmod {2,147,483,563}}$ or $x^{1,073,741,781}\equiv -1{\pmod {2,147,483,563}}$.

Since 40,014 is a primitive root, it is not a quadratic residue, so ${40,014}^{1,073,741,781}\equiv -1{\pmod {2,147,483,563}}$. As a result, this value marks the halfway point of the cycle.

Scientific Calculator Function

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 = ${\frac {500,000,000}{2,147,483,563}}=0.2328306528695...$ 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

• 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 ${40,014}\times {1,601,120,196}\equiv {1,346,387,765}{\pmod {2,147,483,563}}$
  • Fifth term: 439,883,729 because ${40,014}\times {1,346,387,765}\equiv {439,883,729}{\pmod {2,147,483,563}}$
• The sequence of random numbers repeats every 2,147,483,562 terms.
• The multiplicative inverse of 40,014 is 2,082,061,899 because ${40,014}\times {2,082,061,899}\equiv 1{\pmod {2,147,483,563}}$. 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 ${40,014}\times {65,421,664}\equiv -1{\pmod {2,147,483,563}}$. 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 ${\frac {2,147,483,562}{2,147,483,563}}$, which is so close to one, differing from one by only 4.66 × 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

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	${40,014}^{n}{\pmod {m}}$	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