数论/32位线性同余生成器
在 32 位计算机上，伪随机数使用基数 b = 40,014 和模数 m = 2,147,483,563 = 231 − 85 的线性同余生成器生成。由于模数 m = 2,147,483,563 是一个素数，因此根据费马小定理，对于任何不除以 2,147,483,563 的整数 x， 它还表明 x 模 2,147,483,563 的乘法阶必须是 2,147,483,562 或其真因子之一。基数 b = 40,014 是模 2,147,483,563 的本原根，所以这个序列具有 2,147,483,562 的完整周期长度。
对于任何素数 p，费马小定理保证任何不除以 p 的整数 x 都满足以下同余式：
例如，对于素数 p = 13 和基数 x = 2，我们将这些值代入方程：212 = 4,096。费马小定理预测这个数模 13 同余 1。事实上，它是：4,096 = 13 × 315 + 1，所以
在素模中，任何整数最多只有两个平方根。同余式 只有平凡解 a = ± 1 模 p。例如，单位模 13 的唯一平方根是 1 和 12。这对复合模不成立；例如，模 15 的单位有四个平方根：1、4、11 和 14。
由于 2,147,483,563 是一个素数，对于任何不与零模 2,147,483,563 同余的 x： 同样，2,147,483,562 的一半是 1,073,741,781，因此要么 或 .
由于 40,014 是一个本原根，它不是二次剩余，所以 。因此，此值标志着周期的中点。
德州仪器计算器 TI-30X IIS 内置了一个伪随机数生成器，它使用存储在内存中的“rand”的值，可以通过按“MEMVAR”访问。要更改“rand”的值，请按“STO”，按一次左箭头按钮，然后按“ENTER”将一个整数存储到此变量中。一旦一个整数存储到此变量中，它通常会保持不变，仅当生成伪随机数时才会改变。每当生成一个伪随机数时，“rand”的值将根据以下公式改变：（新整数）= 40,014 ×（当前整数）模 2,147,483,563。
要生成一个伪随机数，请按“PRB”并使用“RAND”或“RANDI”。请注意，这里“RAND”全部大写，以区分存储在内存中的整数变量。“RAND”是介于零和一之间的伪随机十进制数，通过将新的“rand”值除以 2,147,483,563 计算得出。例如，如果 rand = 500,000,000，那么 RAND = 德州仪器计算器将小数四舍五入到最接近的十亿分之一，显示小数点后九位数；在本例中，显示为 0.232830653。
RANDI 是一个接受两个参数的函数：RANDI(a, b) 生成一个介于 a 和 b 之间的伪随机整数（包括 a 和 b）。
属性
[edit | edit source]- 循环的第一个项是 1，之后的每一项都通过乘以 40,014 并取模 2,147,483,563 的余数来计算。
- 第二项：40,014
- 第三项：40,014 × 40,014 = 1,601,120,196
- 第四项：1,346,387,765 因为
- 第五项：439,883,729 因为
- 随机数序列每 2,147,483,562 个项重复一次。
- 40,014 的乘法逆元是 2,082,061,899，因为 。数字 2,082,061,899 是循环的最后一项，之后循环从头开始。
- 可以通过将 77,872,045 存储为种子值（在计算器的内存存储中称为“rand”），然后生成 5 个随机数来查看循环的最后 5 项。
- 40,014 的负乘法逆元是 65,421,664，因为 。这标志着循环的中点。
- 由于计算器上 9 位数的精度设置，所有小数值都显示为四舍五入到最接近的十亿分之一，因此在将 65,421,664 存储为种子值后，“RAND”的第一个值显示为等于 1。实际上，此值为 ，它非常接近于 1，与 1 的差仅为 4.66 × 10−10，因此在计算器将其四舍五入到小数点后九位时，它会四舍五入到 1.000000000。
- 数字 65,421,664 是循环前半部分的最后一项。
- 数字 2,147,483,563 − 40,014 = 2,147,443,549 是循环后半部分的第一项。
值表
[edit | edit source]注意：在此表中，m = 2,147,483,563。所有 RAND 值都四舍五入到九位有效数字。虽然科学计算器截断以零结尾的 9 位小数，但此表中将保留最后的零（即，“0.123456000”，而不是“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 |
