C++ 高性能隨機數生成器：Xorshift 算法實現

場景痛點：std::rand() 性能瓶頸

在解決旅行商問題（TSP）時，需對 500+ 節點進行 3-opt 交換優化，要求隨機選取 1/3 以上節點。標準庫 rand() 速度嚴重不足，且受限於無法使用 Boost 等第三方庫，需尋找純標準庫實現的高性能隨機數生成器。

Xorshift 算法：極簡高效的偽隨機數生成器

George Marsaglia 發明的 Xorshift 通過「異或 + 位移」操作生成下一數值，屬於線性反饋移位寄存器（LFSR）子類。特點：

• 極快：現代 CPU 指令流水線下，生成一個隨機數通常 < 10 時鐘週期
• 代碼極短：僅需幾行代碼，狀態極小
• 非加密安全：不適用於加密或高精度蒙特卡洛模擬
• 需精選參數：以確保長週期（如 2^96-1 或 2^128-1）

經典實現：xorshf96 (96-bit 狀態，週期 2^96-1)

static unsigned long x = 123456789, y = 362436069, z = 521288629;

unsigned long xorshf96(void) { // period 2^96-1
    unsigned long t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;

    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;

    return z;
}

適用場景：通用隨機採樣、遊戲邏輯、模擬退火、遺傳算法等對統計分布要求不極嚴格的高性能場景。

已知缺陷：生成二進制矩陣時奇異矩陣分布異常，無法通過 TestU01 BigCrush 的 MatrixRank 和 LinearComp 測試。

進階版：xorshift128+ (128-bit 狀態，通過所有 BigCrush 測試)

#include <cstdint>

// 狀態變量必須非全零初始化
uint32_t x, y, z, w;

uint32_t xorshift128(void) {
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

// xorshift128+ 版本（加入非線性步驟，統計特質大幅提升）
uint64_t s[2]; // 128-bit 狀態

uint64_t xorshift128plus(void) {
    uint64_t s1 = s[0];
    uint64_t s0 = s[1];
    s[0] = s0;
    s1 ^= s1 << 23; // a
    s[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26); // b, c
    return s[1] + s[0];
}

xorshift128+ 在 x86 上生成一個 64-bit 隨機數僅需 <10 時鐘週期，且 BigCrush 失敗次數比 Mersenne Twister、WELL 算法少一個數量級，是非加密場景下的最佳選擇。

工程建議

1. 一般高性能需求：使用 xorshf96 或 xorshift128
2. 需較好統計特質：使用 xorshift128+ 或 xorshift1024*
3. 加密/高精度科學計算：禁用，改用 C++11 <random> 或專用加密庫
4. 種子初始化：務必確保狀態變量非全零，可結合 std::chrono::high_resolution_clock 或硬體熵源