Skip to content

Xorshift

Xorshift 是一类由统计学家 George Marsaglia 于 2003 年提出的伪随机数生成器 (PRNG)。

Xorshift32

Xorshift32 是该系列中最基础、最轻量级的 32 位版本。其核心设计哲学是完全摒弃复杂的算术运算（如乘法、除法或取模），仅通过计算机底层执行速度极快的位异或 (XOR) 和位移 (Bit Shift) 操作来产生高质量的随机数序列。

一、 核心算法与实现

Xorshift32 的内部状态非常小，仅包含一个 32 位的无符号整数。在每次生成新的随机数时，该状态变量会经历三次连续的“移位并与自身异或”的操作。

1. 算法步骤

设当前内部状态为 \(x\)（一个 32 位非零无符号整数）：

  1. 左移与异或： 将 \(x\) 向左移动 13 位，并将结果与原始的 \(x\) 进行按位异或。

  2. 右移与异或： 将上一步的结果向右移动 17 位，并与自身进行按位异或。

  3. 左移与异或： 将上一步的结果向左移动 5 位，再次与自身进行按位异或。

最后得到的值即为生成的伪随机数，同时该值更新为生成器的下一个内部状态。

2. 标准 C 语言实现

#include <stdint.h>

/* 内部状态，必须初始化为非零值 */
uint32_t state = 2463534242;

uint32_t xorshift32(void) {
    uint32_t x = state;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    state = x;
    return x;
}

关键约束（零状态陷阱）： 初始种子（Seed）绝对不能为 0。如果 \(x = 0\)，由于 0 的任何移位仍为 0，且 \(0 \oplus 0 = 0\)，生成器将陷入永远输出 0 的死循环。

二、 数学原理与特性

1. 线性变换的本质

尽管表现形式是位运算，Xorshift 在数学上等价于一种特定类型的线性反馈移位寄存器 (LFSR)。

每一次 Xorshift 操作都可以看作是在有限域 \(\text{GF}(2)\)（即只包含 0 和 1，加法等同于异或的代数系统）上的线性变换。整个 Xorshift32 算法可以表示为当前状态向量乘以一个 \(32 \times 32\) 的非奇异二进制变换矩阵 \(T\)：

\[ x_{n+1} = x_n T \]

2. 最大周期 (Maximal Period)

矩阵 \(T\) 的特征多项式被精心设计为 \(\text{GF}(2)\) 上的本原多项式 (Primitive Polynomial)。这一数学性质保证了 Xorshift32 能够遍历除 0 以外的所有可能状态。

因此，Xorshift32 的周期长度为：

\[ P = 2^{32} - 1 \]

这意味着在连续调用 4,294,967,295 次之后，生成的随机数序列才会开始重复。

三、 算法评估（优缺点分析）

1. 核心优势

  • 极致的性能： 现代 CPU 执行异或和移位指令只需极少的时钟周期。Xorshift 避开了耗时的乘法指令，执行速度通常远超线性同余生成器 (LCG) 或 Mersenne Twister (MT19937)。

  • 极低的空间开销： 状态空间仅需 4 个字节（32 位），非常适合内存极其受限的环境。

  • 优于 LCG 的随机性： 在低维空间中，Xorshift 不像 LCG 那样存在明显的“超平面”聚集缺陷（Marsaglia 效应），在基础的统计测试中表现更好。

2. 存在的缺陷

  • 未能通过严格的统计测试： 尽管比 LCG 优秀，但原版的 Xorshift 算法在面对严苛的 PRNG 测试套件（如 TestU01 的 BigCrush）时会暴露出部分非随机性，特别是在矩阵秩测试 (MatrixRank test) 中容易失败，表明其位级别的线性相关性仍然存在。

  • 零状态脆弱性： 一旦内存错误导致状态变为 0，生成器即宣告失效。

  • 非密码学安全： 由于其纯线性的数学结构，攻击者只需截获少量连续的输出结果，即可通过解线性方程组轻易逆向推导出内部状态，从而预测未来所有的随机数。

四、 演进与应用场景

1. 适用场景

基于其性能和体积优势，Xorshift32 及其变体非常适合以下领域：

  • 嵌入式系统与微控制器： 内存（RAM）和算力极小的单片机。

  • 游戏开发： 用于生成粒子系统、程序化生成地形（Procedural Generation）、非关键逻辑的微小随机事件。

  • 大规模并行计算： 在 GPU 编程中，为每个线程分配一个独立的轻量级 PRNG。

2. 不适用场景

  • 密码学系统： 密钥生成、会话 ID 绝对禁止使用。

  • 高精度科学计算： 严肃的蒙特卡洛模拟（Monte Carlo Simulations）不应使用 Xorshift32，以免线性偏差污染模拟结果。

3. 现代演进

由于纯 Xorshift 存在的线性统计缺陷，后来衍生出了 Xorshift (乘以一个常数) 和 Xorshift+ (两个状态相加) 等非线性改进版本。现代更先进的 PRNG 如 PCG 和 Xoshiro/Xoroshiro* 家族，皆是在 Xorshift 的核心理念基础上增加了扰动函数 (Scrambler)，在保持极高速度的同时完美通过了所有严格的统计测试。

Xorshift64

Xorshift64 是该系列中针对 64 位计算架构设计的核心版本。其核心设计理念与 Xorshift32 一脉相承：完全摒弃加减乘除等算术运算，仅依赖执行速度极快的位异或（XOR） 和位移（Bit Shift） 操作来产生随机数序列。

一、 核心算法与参数选择

Xorshift64 的内部状态由单一的 64 位无符号整数构成。每次生成新的随机数时，状态变量会经历三次特定的“移位并与自身异或”操作。

1. 算法步骤与移位三元组

设当前内部状态为 \(x\)（一个 64 位非零无符号整数），算法执行以下三步：

  1. 左移与异或： \(x \leftarrow x \oplus (x \ll a)\)

  2. 右移与异或： \(x \leftarrow x \oplus (x \gg b)\)

  3. 左移与异或： \(x \leftarrow x \oplus (x \ll c)\)

为了保证生成器能够达到最大周期，位移参数 \((a, b, c)\) 必须经过严格的数学筛选。根据 Marsaglia 的论文，对于 64 位状态，存在多组满足全周期的移位常数三元组。其中最经典且广泛使用的一组参数是 \([13, 7, 17]\)。

2. 标准 C 语言实现

#include <stdint.h>

/* 内部状态，必须初始化为非零值 */
uint64_t state = 88172645463325252ULL;

uint64_t xorshift64(void) {
    uint64_t x = state;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    state = x;
    return x;
}

核心约束（零状态陷阱）： 初始种子（Seed）绝对不能为 0。若状态变量变为 0，所有移位和异或操作的结果将永远为 0，生成器会彻底失效并陷入死循环。

二、 数学原理与统计特性

1. 线性变换与最大周期

在数学本质上，Xorshift64 等价于有限域 \(\text{GF}(2)\) 上的线性反馈移位寄存器（LFSR）。其运算过程可以抽象为一个 \(64 \times 64\) 的二进制非奇异变换矩阵 \(T\) 与当前状态向量的乘法运算：

\[ x_{n+1} = x_n T \]

当且仅当该矩阵 \(T\) 的特征多项式是 \(\text{GF}(2)\) 上的本原多项式时，该生成器才能遍历除 0 以外的所有 \(2^{64}-1\) 个状态。

因此，经过特定参数（如 \([13, 7, 17]\)）配置的 Xorshift64，其周期长度严格为：

\[ P = 2^{64} - 1 \]

2. 统计学缺陷（线性相关性）

纯粹的 Xorshift 算法本质上是完全线性的。这种纯线性结构导致其在严苛的统计学测试中暴露出固有缺陷：

  • 矩阵秩测试失败： 在 TestU01 随机性测试套件（特别是 BigCrush 级别）中，Xorshift64 会在矩阵秩测试（MatrixRank test）和线性复杂度测试中明确失败。

  • 位层面的规律性： 生成的 64 位数据中，某些位之间存在可被数学工具捕捉到的线性相关性，这意味着它在多维空间中的分布并非绝对均匀无规律。

三、 算法评估与应用场景分析

1. 显著优势

  • 执行速度极速： 不包含任何乘法、除法或取模指令。在现代 64 位 CPU 上，三次位运算几乎可以在 1 到 2 个时钟周期内完成，吞吐量极大。

  • 内存开销极低： 整个状态机仅占用 8 字节（64 位）内存。对于需要实例化数百万个独立随机数生成器的并发场景极其友好。

  • 长周期保障： \(2^{64}-1\) 的周期对于绝大多数非加密级别的常规计算任务而言已经足够庞大，远超 32 位生成器。

2. 致命劣势

  • 非密码学安全： 纯线性特征使得攻击者在获取少量连续输出（例如连续 64 个位的数据）后，即可通过高斯消元法解线性方程组，瞬间还原内部状态，进而预测未来和过去的全部随机数序列。

  • 不适合高维模拟： 由于未能通过 BigCrush 测试，在对随机性要求极高的蒙特卡洛积分（Monte Carlo integration）或大规模物理粒子模拟中，使用该算法可能导致结果出现偏差。

3. 典型适用场景

  • 游戏引擎内部逻辑： 用于生成地图元素、控制 NPC 行为或粒子发射器等不需要密码学保护的模块。

  • 海量并行计算（如 GPU 编程）： 在 CUDA 或 OpenCL 环境下，为每个计算线程分配独立的 PRNG 时，Xorshift64 的低寄存器占用特性使其成为理想选择。

四、 现代演进：打破线性魔咒

为了弥补纯 Xorshift64 的线性缺陷，学术界在此基础之上引入了非线性扰动函数（Scrambler），衍生出了一系列现代高质量 PRNG：

  • Xorshift64* (Star)： 在原本的 Xorshift64 结果输出前，将其乘以一个精心挑选的 64 位奇数常数（例如 0x2545F4914F6CDD1D）。乘法操作极大地破坏了位运算的线性特性，使其能够顺利通过大多数严格的统计测试，且性能损耗极小。

  • Xoshiro / Xoroshiro 家族： 原作者的继承者 Sebastiano Vigna 进一步对状态数组和操作顺序进行重构，开发出了 Xoshiro256** 等现代生成器。这些新算法不仅保留了 Xorshift 的极致性能，同时完美通过了所有已知的统计学测试，目前已被广泛纳入各主流编程语言的标准库中。