不使用 Math.random() 生成隨機數：Java 多線程競態隨機算法深度解析

背景與動機

本文分析一種不依賴 JDK 內建隨機函數、純利用多線程調度非確定性構建的隨機數生成器。雖然生產不可用，但作為「系統熵源挖掘」的教學案例極具啟發性。

算法核心架構

┌─────────────────────────────────────────────────────────────┐
│ 共享狀態（靜態字段）                                           │
│  - R[65536] : LCG 生成的查找表                                 │
│  - f (AtomicInteger) : 當前索引指針                           │
│  - randomValue : 最新隨機值                                   │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│ 工作線程 (Runnable)                                           │
│  while (!interrupted) {                                       │
│      f = (f/2 + R[f]) % 65536   // 狀態遷移                   │
│      randomValue = R[f]         // 輸出                       │
│  }                                                            │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│ 主控流程 (13 輪疊代放大)                                       │
│  for i in 0..12:                                              │
│      啟動工作線程 → sleep(極短) → interrupt → 采樣 randomValue │
│      動態調整參數 (x, shuffleR)                                │
│      檢測不動點 → 強制打亂                                     │
│  返回第 13 次采樣                                             │
└─────────────────────────────────────────────────────────────┘

關鍵組件詳細解析

1. 線性同餘生成器 (LCG) 初始化 R 陣列

R[0] = 13849;
for i = 1 to 65535:
    R[i] = (2053 * R[i-1] + 13849) % 65536
// 參數選擇：m=2^16, a=2053, c=13849 滿足 Hull-Dobell 定理，周期最大 65536

生成 0~65535 的全排列（若參數得當），作為確定性查找表。

2. 狀態遷移函數

f_{next} = (f/2 + R[f]) mod M

• f/2：右移一位，引入低位變化
• R[f]：查表引入非線性
• 組合形成混沌映射，極敏感於初始條件

3. 13 輪疊代放大（胡蝶效應工程化）

4. 陣列循環移位

void shuffleR(int shift) {
    int[] copy = R.clone();
    for i in 0..M-1: R[i] = copy[(i + shift) % M];
}

O(M) 操作但 M=65536 固定，實際耗時 ~0.1ms。改變查找表順序，打破潛在週期。

為什麼這不可用於生產？

正確的「不使用 Math.random()」方案

若因特殊原因不能用 Math.random()（Random 實例），請用：

// 1. ThreadLocalRandom (JDK 7+) - 最推薦
ThreadLocalRandom.current().nextDouble();

// 2. SecureRandom - 加密級
new SecureRandom().nextDouble();

// 3. 自定義種子 Random - 可復現
new Random(12345L).nextDouble();

// 4. SplittableRandom (JDK 8+) - 並行流
new SplittableRandom().nextDouble();

// 5. 純算法實現 (Xorshift/Xoshiro) - 無依賴、極快
// 參考 Vigna 的論文，幾行代碼實現高質量 PRNG

教學價值總結

該算法雖不可用，但展示了隨機數生成的核心哲學：

1. 熵源：物理非確定性（熱噪聲、時鐘抖動、調度抖動）
2. 提取：將熵源轉為比特流（此處用線程競態）
3. 擴展/白化：通過非線性變換放大熵、消除偏態（此處用 13 輪疊代 + 陣列打亂）
4. 輸出：格式化為所需分布

現代 CPU 指令集（RDRAND、RDSEED）直接提供硬件熵源，OS (/dev/urandom, CryptGenRandom) 做提取白化，JDK SecureRandom 封裝調用。理解這一層次，才算真正懂隨機數。