數論/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 |
