aiwiki.page
中文

Xorshift

Xorshift 是一类高速伪随机数生成器,通过按位异或与移位运算更新内部状态。

17 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
伪随机数生成器异或C 编程语言向量空间有限域矩阵(数学)多项式图形处理单元Xorshift

Xorshift 是一类伪随机数生成器,通过一系列按位异或(XOR)与移位运算更新内部状态。这类生成器由乔治·马萨利亚(George Marsaglia)于 2003 年提出,以状态占用小、实现简单和运行速度快著称。其状态转移在二元域上是线性的,因此周期便于进行数学分析,但也会产生可检测的统计结构。后续变体增加了乘法、加法等输出变换,以减轻其中一些弱点。基本的 xorshift 及其常用的输出扰乱变体都不具备密码学安全性。

基本运作方式

xorshift 生成器保存一个固定大小的二进制状态,并反复使用以下形式的运算对其进行修改:

x←x⊕(x≪a)x \leftarrow x \oplus (x \ll a)

或

x←x⊕(x≫b),x \leftarrow x \oplus (x \gg b),

其中,⊕\oplus 表示异或,≪\ll 表示左移,≫\gg 表示逻辑右移。逻辑右移将空出的位置补零;固定位宽的左移则丢弃移出字边界的位。

每次运算都将当前状态与其自身的一个移位副本进行组合。典型的单字生成器执行三次这样的运算,交替使用不同的移位方向,并将所得状态作为下一次输出返回。

以下用 C编程语言编写的实现通常称为 xorshift32:

#include <stdint.h>

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

当初始状态非零时,这个特定生成器的周期为 232−12^{32}-1。如果初始状态为零,状态就会一直保持为零。

移位量及其执行顺序都是生成器定义的一部分。随意更换这些常数,并不一定能保持最大周期或可接受的统计表现。

数学结构

二元域上的线性性

一个 nn 位状态可以视为向量空间 F2n\mathbb{F}_2^n 中的向量,其中 F2\mathbb{F}_2 是仅包含零和一的有限域。在这种表述下,异或就是向量加法,而固定的移位运算则是线性变换。

因此,一次完整的 xorshift 更新可以用二进制矩阵 TT 表示:

st+1=Tst.s_{t+1}=T s_t.

经过 kk 次更新后,

st+k=Tkst.s_{t+k}=T^k s_t.

这种结构将 xorshift 生成器与线性反馈移位寄存器联系起来。两者都通过二元域上的线性递推生成确定性序列,不过 xorshift 的实现围绕高效的字级运算来组织计算。

可逆性与最大周期

当移位量严格大于零且小于字宽时,x←x⊕(x≪a)x \leftarrow x \oplus (x \ll a) 这样的运算是可逆的。原始位可以从字中未发生变化的一端开始逐步恢复。相应的右移运算也是可逆的。

因此,这些运算的复合构成状态空间上的一个置换。零始终是一个不动点,所以其余 nn 位状态所能构成的最长循环长度为

P=2n−1.P=2^n-1.

并非每一种可逆转移都能达到这一周期。判断线性转移是否具有满周期的一项标准判据,是其特征多项式是否为 F2\mathbb{F}_2 上的本原多项式。因此,合适的移位参数必须通过数学分析或等价的周期测试来确定。

对于满周期生成器,每个非零状态在一个周期内恰好出现一次。这描述的是状态的覆盖情况,并不保证较短的输出序列表现得像相互独立的随机样本。

状态大小与输出大小

最简单的变体将一个机器字同时用作状态和输出。其他设计则维护多个字,但每次更新只返回一个字。例如,经典的 xorshift128 使用四个 32 位字,可以达到 2128−12^{128}-1 的周期。

更大的状态增加了可能达到的周期长度,却不能消除线性依赖关系。状态大小、输出位宽、周期和统计质量是不同的属性。

历史与相关系列

马萨利亚在 2003 年发表的论文《Xorshift RNGs》中,提出了基于移位与异或组合的生成器,包括单字和多字形式。与需要更多算术运算或更大状态数组的生成器相比,它们提供了一种开销较小的替代方案。

后续研究着重于在不牺牲底层状态转移速度的前提下改善统计表现。由此形成了一个重要区分:

  • 状态转移: 推进内部状态的规则。
  • 输出函数: 将一个状态或多个状态字转换为返回给程序的数值的规则。

生成器可以保留线性状态转移,同时使用在 F2\mathbb{F}_2 上非线性的输出函数。这通常称为扰乱(scrambling)。

仅凭 xorshift32 和 xorshift128 这样的名称,并不能确定实现的全部细节。要明确指定一个序列,还需要知道移位常数、更新顺序、字的排列方式以及输出的选取方式。

主要变体

基本 xorshift

基本 xorshift 生成器直接返回一个状态字,不进行非线性输出变换。其优点是计算量极小,实现也很直接。

它的主要局限在于二进制线性结构直接暴露在输出中。即使周期很长,专门用于识别线性关系的统计测试仍能将其输出与独立随机比特区分开来。

Xorshift*

xorshift* 生成器将一个由状态得到的字乘以固定的奇数常量;对于 ww 位输出,运算以 2w2^w 为模进行:

yt=cxt(mod2w).y_t=cx_t \pmod{2^w}.

奇数乘数在模 2w2^w 下可逆,因此这一变换是所有可能字值上的一个置换。乘法产生的进位引入了 F2\mathbb{F}_2 上的非线性,从而改善了许多统计性质。

这一变换并不能消除所有弱点。特别是,乘以奇数常量不会改变最低有效位:

yt mod 2=xt mod 2.y_t \bmod 2=x_t \bmod 2.

当可逆乘法应用于完整状态输出时,对于了解生成器的观察者而言,它也无法隐藏状态。

Xorshift+

xorshift+ 生成器通过将选定的状态字按模 2w2^w 相加来生成输出:

yt=ut+vt(mod2w).y_t=u_t+v_t \pmod{2^w}.

进位运算引入了二进制非线性。Xorshift128+ 是其中一个知名例子,它使用 128 位状态,生成 64 位输出。

输出的最低位仍然是相应输入位的异或,因为没有进位传入这一位。因此,基于加法的扰乱并不能消除低位中的所有线性结构。

XORWOW

XORWOW 将 xorshift 递推与一个加法计数器结合起来,后者通常被描述为外尔序列。计数器每次增加一个固定的奇数增量,以二的某个幂为模,并与 xorshift 输出进行组合。

这种构造为生成器引入了一个独立的组成部分,而不只是对一个状态字施加无状态变换。它已被用于图形处理器上的随机数生成。

Xoroshiro 与 xoshiro

Xoroshiro 和 xoshiro 是与 xorshift 相关的后继系列,除异或和移位外,还使用循环移位。它们的名称指代其状态转移中所使用的运算。

它们并非只是原始三次移位递推的另一组参数。不同成员采用不同的状态布局和输出扰乱函数,包括 +、++ 和 ** 等形式。针对某个成员得出的统计结论,并不自动适用于其他所有成员。

统计质量

长周期是许多用途的必要条件,但不足以证明随机性质量很高。一个序列即使遍历了数量极其庞大的状态,仍可能保留可利用的相关性。

基本 xorshift 的输出尤其容易被涉及二元线性代数的测试识别,包括矩阵秩测试和线性复杂度测试。这些测试会检查采样比特所满足的线性关系,是否多于独立随机数据中预期出现的数量。

TestU01 等测试套件会评估多项统计性质。结果取决于具体生成器、所检查的输出位、样本量,以及向测试提供输出的方式。对完整输出字、仅最低若干位或比特顺序反转后的版本进行测试,可能暴露不同的弱点。

扰乱通常能改善统计测试中的表现,但并不能确立独立性,也不能证明生成器适合所有模拟。同样,通过有限的一组测试并不能确立密码学安全性。

实现与可复现性

种子初始化

xorshift 的整个状态不能全为零。对于多字生成器,只要完整状态满足生成器的要求,个别字可以为零。

非零种子可以避免进入吸收性的零状态,但不能保证彼此接近的种子会产生充分分离的初始序列。较大的生成器通常使用独立的混合过程进行初始化,将一个种子扩展为所需的状态。

要实现可复现的计算,必须明确指定生成器变体、初始化方法、输出转换方式和状态。

字运算

实现依赖于固定位宽的二进制运算。重要细节包括:

  • 在需要逻辑右移时使用无符号值。
  • 保持规定的字宽。
  • 对乘法和加法扰乱函数使用模运算。
  • 避免使用超出语言允许范围的移位量。

有符号移位和整数溢出的语义因语言而异,可能导致表面相似的实现产生不同的行为。

输出转换

原始随机字并不会自动成为任意区间内均匀分布的值。如果源值域的大小不能被 mm 整除,将输出对 mm 取模就可能引入偏差。

同样,将字转换为浮点数也需要明确定义映射方式。实现通常在构造二进制小数时选取高位,但这会改变底层输出的哪些性质会影响最终结果。

这些转换问题独立于 xorshift 递推本身,也会影响其他生成器系列。

并行随机流

由于状态转移是线性的,生成器可以支持基于 TT 的幂的跳跃推进操作。这类操作能将状态向前推进一个较大的固定距离,而不必生成中间的每一个输出。

这在并行计算中很有用,因为可以为各工作单元分配序列中相互分隔的片段。仅使用不同种子并不能确立随机流的独立性:对于满周期递推,所有非零状态都位于同一个循环上。要避免重叠,必须注意随机流之间的间隔以及所消耗的输出数量。

应用与局限

基于 xorshift 的生成器用于模拟、程序化内容生成、计算机图形学、测试和随机化算法等重视速度与可复现性的场景。当需要同时维护大量生成器实例时,其紧凑的状态可能很有用。

是否适用取决于具体变体和工作负载。32 位状态的非零状态数量少于 4.34.3 十亿,因此对于高吞吐量或长时间运行的计算,其周期较短。更大的状态可以解决周期长度问题,而输出扰乱可以改善一部分统计弱点,但并非全部。

Xorshift 生成器不适合密钥生成、秘密令牌和不可预测的挑战值等密码学用途。在基本变体中,输出可能直接暴露状态,或提供可用于恢复状态的线性方程。常见扰乱运算的设计目标是改善统计质量,而不是抵抗密码分析。统计随机性与抵抗攻击者预测的能力是不同的要求。