Xorshift算法详解：高效伪随机数生成的利器

Xorshift算法是一种快速、轻量级的伪随机数生成器，由George Marsaglia于2003年提出。它以极少的计算量生成高质量的随机数序列，广泛应用于游戏开发、模拟和需要高性能随机数生成的场景。

一、算法核心原理

1. 基本思想

Xorshift基于线性反馈移位寄存器(LFSR)的变体，通过位移(shift)和异或(XOR)操作来改变内部状态。

2. 数学表示

对于32位版本，典型操作为：

x ^= x << a
x ^= x >> b  
x ^= x << c

其中 a, b, c 是精心选择的常数。

二、完整算法实现

1. 不同位宽的Xorshift实现

<?php

/**
 * Xorshift家族算法实现
 */
class XorshiftFamily {
    // 常用参数组合（经过验证的优质参数）
    private const PARAMS = [
        // 32位版本
        '32' => [
            [13, 17, 5],    // 最常见
            [13, 19, 3],
            [15, 18, 2],
        ],
        // 64位版本  
        '64' => [
            [13, 7, 17],
            [21, 35, 4],
            [13, 7, 37],
        ],
        // 128位版本
        '128' => [
            [11, 8, 19], [19, 3, 23]
        ]
    ];
    
    /**
     * 基础Xorshift32（单状态变量）
     */
    class Xorshift32 {
        private $state;
        
        public function __construct($seed = null) {
            $this->state = $seed ?? mt_rand(0, 0xffffffff);
            // 确保状态不为0（0会导致始终为0）
            if ($this->state == 0) {
                $this->state = 1;
            }
        }
        
        public function nextInt(): int {
            $x = $this->state;
            $x ^= $x << 13;
            $x ^= $x >> 17;
            $x ^= $x << 5;
            $this->state = $x & 0xffffffff;
            return $this->state;
        }
        
        public function nextFloat(): float {
            return $this->nextInt() / 0xffffffff;
        }
        
        public function getState(): int {
            return $this->state;
        }
        
        public function setState($state): void {
            $this->state = $state & 0xffffffff;
            if ($this->state == 0) {
                $this->state = 1;
            }
        }
    }
    
    /**
     * Xorshift64（64位版本）
     */
    class Xorshift64 {
        private $state;
        
        public function __construct($seed = null) {
            $seed = $seed ?? (mt_rand(0, 0xffffffff) << 32) | mt_rand(0, 0xffffffff);
            $this->state = $seed & 0xffffffffffffffff;
            if ($this->state == 0) {
                $this->state = 1;
            }
        }
        
        public function nextInt(): int {
            $x = $this->state;
            $x ^= $x << 13;
            $x ^= $x >> 7;
            $x ^= $x << 17;
            $this->state = $x & 0xffffffffffffffff;
            return $this->state >> 32; // 返回32位随机数
        }
        
        public function nextFloat(): float {
            $intVal = $this->nextInt() & 0xffffffff;
            return $intVal / 0xffffffff;
        }
        
        public function nextInt64(): int {
            $x = $this->state;
            $x ^= $x << 13;
            $x ^= $x >> 7;
            $x ^= $x << 17;
            $this->state = $x & 0xffffffffffffffff;
            return $this->state;
        }
    }
    
    /**
     * Xorshift128（4个32位状态，周期更长）
     */
    class Xorshift128 {
        private $state = [0, 0, 0, 0];
        
        public function __construct($seed = null) {
            if ($seed === null) {
                $seed = mt_rand(0, 0xffffffff);
            }
            
            // 用种子初始化4个状态变量
            $s = $seed & 0xffffffff;
            $this->state[0] = $s;
            $this->state[1] = ($s ^ 0x9e3779b9) & 0xffffffff; // 黄金分割率
            $this->state[2] = ($s << 16) & 0xffffffff;
            $this->state[3] = ($s >> 16) & 0xffffffff;
            
            // 确保没有全0状态
            if ($this->state[0] == 0 && $this->state[1] == 0 && 
                $this->state[2] == 0 && $this->state[3] == 0) {
                $this->state[0] = 1;
            }
            
            // 热身（丢弃前几个输出）
            for ($i = 0; $i < 10; $i++) {
                $this->nextInt();
            }
        }
        
        public function nextInt(): int {
            // Xorshift128+ 变体（更好的统计特性）
            $s1 = $this->state[0];
            $s0 = $this->state[1];
            
            $this->state[0] = $s0;
            $s1 ^= $s1 << 23;
            
            $this->state[1] = $s1 ^ $s0 ^ ($s1 >> 17) ^ ($s0 >> 26);
            $this->state[2] = $this->state[3];
            $this->state[3] = $s0;
            
            return ($this->state[1] + $s0) & 0xffffffff;
        }
        
        public function getState(): array {
            return $this->state;
        }
    }
    
    /**
     * Xorshift*（改进版本，乘以常数）
     */
    class XorshiftStar {
        private $state;
        
        public function __construct($seed = null) {
            $this->state = $seed ?? mt_rand(0, 0xffffffff);
            if ($this->state == 0) {
                $this->state = 1;
            }
        }
        
        public function nextInt(): int {
            $x = $this->state;
            $x ^= $x >> 12;
            $x ^= $x << 25;
            $x ^= $x >> 27;
            $this->state = $x & 0xffffffff;
            
            // 乘以常数改进分布
            return ($this->state * 0x2545F4914F6CDD1D) & 0xffffffff;
        }
    }
    
    /**
     * Xoroshiro128+（更现代的变体）
     */
    class Xoroshiro128Plus {
        private $state = [0, 0];
        
        public function __construct($seed = null) {
            if ($seed === null) {
                $seed = mt_rand(0, 0xffffffff);
            }
            
            $s = $seed & 0xffffffff;
            $this->state[0] = $s;
            $this->state[1] = ($s ^ 0x9e3779b9) & 0xffffffff;
            
            // 热身
            for ($i = 0; $i < 10; $i++) {
                $this->nextInt();
            }
        }
        
        public function nextInt(): int {
            $s0 = $this->state[0];
            $s1 = $this->state[1];
            $result = ($s0 + $s1) & 0xffffffff;
            
            $s1 ^= $s0;
            $this->state[0] = (($s0 << 55) | ($s0 >> 9)) ^ $s1 ^ ($s1 << 14);
            $this->state[1] = ($s1 << 36) | ($s1 >> 28);
            
            return $result;
        }
        
        public function jump(): void {
            // 实现跳跃函数，用于并行生成多个不重叠序列
            $jump = [0xbeac0467eba5facb, 0xd86b048b86aa9922];
            
            $s0 = 0;
            $s1 = 0;
            
            for ($i = 0; $i < count($jump); $i++) {
                for ($b = 0; $b < 64; $b++) {
                    if ($jump[$i] & (1 << $b)) {
                        $s0 ^= $this->state[0];
                        $s1 ^= $this->state[1];
                    }
                    $this->nextInt();
                }
            }
            
            $this->state[0] = $s0;
            $this->state[1] = $s1;
        }
    }
}

?>

三、算法特性分析

1. 周期长度

算法变体	状态大小	周期长度	备注
Xorshift32	32位	2³²-1	约42.9亿
Xorshift64	64位	2⁶⁴-1	约1.84×10¹⁹
Xorshift128	128位	2¹²⁸-1	约3.4×10³⁸
Xoroshiro128+	128位	2¹²⁸-1	现代变体

2. 速度对比

<?php

class XorshiftBenchmark {
    public static function run() {
        $iterations = 1000000;
        
        $generators = [
            'mt_rand' => function() { return mt_rand(); },
            'xorshift32' => (new XorshiftFamily\Xorshift32())->nextInt(...),
            'xorshift128' => (new XorshiftFamily\Xorshift128())->nextInt(...),
            'xorshift*' => (new XorshiftFamily\XorshiftStar())->nextInt(...),
        ];
        
        $results = [];
        
        foreach ($generators as $name => $generator) {
            $start = microtime(true);
            
            for ($i = 0; $i < $iterations; $i++) {
                $generator();
            }
            
            $end = microtime(true);
            $time = $end - $start;
            $results[$name] = [
                'time' => $time,
                'rate' => $iterations / $time
            ];
        }
        
        return $results;
    }
}

// 运行基准测试
$benchmark = XorshiftBenchmark::run();
foreach ($benchmark as $name => $data) {
    echo sprintf("%-15s: %6.2f ms, %8.0f ops/sec\n", 
        $name, 
        $data['time'] * 1000, 
        $data['rate']
    );
}

?>

典型结果：

• Xorshift32: 比 mt_rand 快 2-3 倍
• Xorshift128: 比 mt_rand 快 1.5-2 倍
• Xorshift*: 略慢于基础版本，但分布更好

四、数学原理详解

1. 线性变换的矩阵表示

Xorshift操作可以表示为GF(2)上的线性变换：

<?php

/**
 * Xorshift的矩阵表示
 */
class XorshiftMatrix {
    /**
     * 将Xorshift操作表示为32×32的矩阵（GF(2)）
     */
    public static function getXorshiftMatrix($a = 13, $b = 17, $c = 5) {
        $size = 32;
        $matrix = array_fill(0, $size, array_fill(0, $size, 0));
        
        // 单位矩阵
        $identity = [];
        for ($i = 0; $i < $size; $i++) {
            $identity[$i] = array_fill(0, $size, 0);
            $identity[$i][$i] = 1;
        }
        
        // 构建左移矩阵 L_a
        $L = $identity;
        for ($i = 0; $i < $size; $i++) {
            if ($i + $a < $size) {
                $L[$i][$i + $a] = 1;
            }
        }
        
        // 构建右移矩阵 R_b
        $R = $identity;
        for ($i = 0; $i < $size; $i++) {
            if ($i - $b >= 0) {
                $R[$i][$i - $b] = 1;
            }
        }
        
        // 计算复合矩阵: M = (I ⊕ L_c)(I ⊕ R_b)(I ⊕ L_a)
        $temp = self::matrixAdd($identity, $L, $a); // I ⊕ L_a
        $temp = self::matrixMultiply(self::matrixAdd($identity, $R, $b), $temp); // (I ⊕ R_b)(...)
        $result = self::matrixMultiply(self::matrixAdd($identity, $L, $c), $temp); // (I ⊕ L_c)(...)
        
        return $result;
    }
    
    /**
     * 矩阵加法（GF(2)上的异或）
     */
    private static function matrixAdd($A, $B, $shift = 0) {
        $size = count($A);
        $result = array_fill(0, $size, array_fill(0, $size, 0));
        
        for ($i = 0; $i < $size; $i++) {
            for ($j = 0; $j < $size; $j++) {
                $result[$i][$j] = ($A[$i][$j] + $B[$i][$j]) % 2;
            }
        }
        
        return $result;
    }
}

?>

2. 可逆性证明

Xorshift操作是可逆的，这意味着存在逆操作：

<?php

/**
 * Xorshift逆变换
 */
class XorshiftInverse {
    /**
     * 逆Xorshift32变换
     * 给定output，求可能的输入state
     */
    public static function reverseXorshift32($output, $a = 13, $b = 17, $c = 5) {
        // 由于输出取了绝对值，可能有多个解
        $possibleStates = [];
        
        // 考虑正负两种情况
        $positive = $output;
        $negative = -$output & 0xffffffff;
        
        foreach ([$positive, $negative] as $state) {
            // 尝试逆变换
            $reversed = self::inverseTransform($state, $a, $b, $c);
            if ($reversed !== null) {
                $possibleStates[] = $reversed;
            }
        }
        
        return $possibleStates;
    }
    
    private static function inverseTransform($y, $a, $b, $c) {
        // 逆第三阶段: y = x ^ (x << c)
        $x = $y;
        for ($i = 31; $i >= 0; $i--) {
            if ($i >= $c) {
                $bit = ($x >> ($i - $c)) & 1;
                $x ^= $bit << $i;
            }
        }
        
        // 逆第二阶段: x = w ^ (w >> b)
        $w = $x;
        for ($i = 0; $i < 32; $i++) {
            if ($i + $b < 32) {
                $bit = ($w >> ($i + $b)) & 1;
                $w ^= $bit << $i;
            }
        }
        
        // 逆第一阶段: w = z ^ (z << a)
        $z = $w;
        for ($i = 31; $i >= 0; $i--) {
            if ($i >= $a) {
                $bit = ($z >> ($i - $a)) & 1;
                $z ^= $bit << $i;
            }
        }
        
        return $z;
    }
}

?>

五、改进与变体

1. Xorshift+（改善低维分布）

<?php

class XorshiftPlus {
    private $state0;
    private $state1;
    
    public function __construct($seed = null) {
        $seed = $seed ?? mt_rand();
        $this->state0 = $seed;
        $this->state1 = $seed ^ 0x9e3779b9;
        
        // 热身
        $this->nextInt();
        $this->nextInt();
    }
    
    public function nextInt(): int {
        $x = $this->state0;
        $y = $this->state1;
        
        $this->state0 = $y;
        $x ^= $x << 23;
        $this->state1 = $x ^ $y ^ ($x >> 17) ^ ($y >> 26);
        
        return ($this->state1 + $y) & 0xffffffff;
    }
    
    /**
     * 生成[0,1)的浮点数（53位精度）
     */
    public function nextDouble(): float {
        $high = $this->nextInt() & 0x1fffff; // 21位
        $low = $this->nextInt() & 0xffffffff; // 32位
        
        // 组合成53位整数，然后除以2^53
        $value = ($high << 32) | $low;
        return $value / 9007199254740992.0; // 2^53
    }
}

?>

2. Xorshift128++（进一步改进）

<?php

class Xorshift128PlusPlus {
    private $state = [0, 0, 0, 0];
    
    public function __construct($seed = null) {
        $seed = $seed ?? mt_rand();
        
        // 更好的初始化
        $this->state[0] = $seed;
        $this->state[1] = $seed ^ 0x9e3779b9;
        $this->state[2] = ($seed << 16) | ($seed >> 16);
        $this->state[3] = ~$seed;
        
        // 长热身
        for ($i = 0; $i < 20; $i++) {
            $this->nextInt();
        }
    }
    
    public function nextInt(): int {
        $s1 = $this->state[0];
        $s0 = $this->state[1];
        $this->state[0] = $s0;
        
        $s1 ^= $s1 << 23;
        $s1 ^= $s1 >> 18;
        $this->state[1] = $s1 ^ $s0 ^ ($s1 >> 5) ^ ($s0 >> 6);
        
        $this->state[2] = $this->state[3];
        $this->state[3] = $s0;
        
        return ($this->state[1] + $s0 + $this->state[2]) & 0xffffffff;
    }
}

?>

六、应用场景

1. 游戏开发中的随机生成

<?php

/**
 * 游戏随机系统（使用Xorshift）
 */
class GameRandomSystem {
    private $rng;
    private $seed;
    
    public function __construct($seed = null) {
        $this->seed = $seed ?? time();
        $this->rng = new XorshiftFamily\Xorshift128($this->seed);
        
        // 记录种子用于调试
        $this->logSeed();
    }
    
    /**
     * 生成随机位置
     */
    public function randomPosition($minX, $maxX, $minY, $maxY): array {
        return [
            'x' => $this->randomInt($minX, $maxX),
            'y' => $this->randomInt($minY, $maxY)
        ];
    }
    
    /**
     * 加权随机选择
     */
    public function weightedChoice(array $items, array $weights) {
        $totalWeight = array_sum($weights);
        $random = $this->randomFloat(0, $totalWeight);
        
        $cumulative = 0;
        foreach ($items as $i => $item) {
            $cumulative += $weights[$i];
            if ($random <= $cumulative) {
                return $item;
            }
        }
        
        return end($items);
    }
    
    /**
     * 洗牌（Fisher-Yates算法）
     */
    public function shuffle(array $array): array {
        $result = $array;
        $count = count($result);
        
        for ($i = $count - 1; $i > 0; $i--) {
            $j = $this->randomInt(0, $i);
            list($result[$i], $result[$j]) = [$result[$j], $result[$i]];
        }
        
        return $result;
    }
    
    /**
     * 生成随机姓名
     */
    public function randomName(): string {
        $prefixes = ['A', 'Be', 'De', 'El', 'Fa', 'Jo', 'Ki', 'La', 'Ma', 'Na', 'O', 'Pa', 'Re', 'Si', 'Ta', 'Va'];
        $suffixes = ['an', 'ar', 'el', 'en', 'ia', 'ic', 'ie', 'in', 'is', 'on', 'or', 'us', 'yn', 'yth'];
        
        $prefix = $prefixes[$this->randomInt(0, count($prefixes) - 1)];
        $suffix = $suffixes[$this->randomInt(0, count($suffixes) - 1)];
        
        return $prefix . $suffix;
    }
    
    private function randomInt($min, $max): int {
        $range = $max - $min + 1;
        return $min + ($this->rng->nextInt() % $range);
    }
    
    private function randomFloat($min, $max): float {
        $range = $max - $min;
        return $min + ($this->rng->nextFloat() * $range);
    }
}

?>

2. 蒙特卡洛模拟

<?php

class MonteCarloSimulation {
    private $rng;
    
    public function __construct() {
        $this->rng = new XorshiftFamily\Xorshift128();
    }
    
    /**
     * 估算圆周率π
     */
    public function estimatePi($iterations = 1000000): float {
        $inside = 0;
        
        for ($i = 0; $i < $iterations; $i++) {
            $x = $this->rng->nextFloat(); // [0, 1)
            $y = $this->rng->nextFloat();
            
            // 检查点是否在单位圆内
            if ($x * $x + $y * $y <= 1.0) {
                $inside++;
            }
        }
        
        return 4.0 * $inside / $iterations;
    }
    
    /**
     * 期权定价（Black-Scholes蒙特卡洛模拟）
     */
    public function optionPrice(
        float $S0,    // 当前股价
        float $K,     // 行权价
        float $r,     // 无风险利率
        float $sigma, // 波动率
        float $T,     // 到期时间（年）
        int $iterations = 100000
    ): float {
        $total = 0;
        
        for ($i = 0; $i < $iterations; $i++) {
            // 生成标准正态分布随机数（Box-Muller变换）
            $u1 = $this->rng->nextFloat();
            $u2 = $this->rng->nextFloat();
            
            $z0 = sqrt(-2.0 * log($u1)) * cos(2.0 * M_PI * $u2);
            
            // 计算到期股价
            $ST = $S0 * exp(($r - 0.5 * $sigma * $sigma) * $T + $sigma * sqrt($T) * $z0);
            
            // 计算期权收益
            $payoff = max($ST - $K, 0);
            $total += $payoff;
        }
        
        // 贴现求现值
        $meanPayoff = $total / $iterations;
        return exp(-$r * $T) * $meanPayoff;
    }
}

?>

七、安全性分析

1. 不是密码学安全的

重要警告：Xorshift不适用于密码学！

<?php

/**
 * 演示Xorshift的预测攻击
 */
class XorshiftPredictor {
    /**
     * 通过观察输出序列预测后续值
     */
    public static function predict(array $observed, $a = 13, $b = 17, $c = 5) {
        if (count($observed) < 2) {
            throw new Exception("需要至少2个观察值");
        }
        
        // 尝试从观察值恢复状态
        $possibleStates = [];
        
        // 对每个可能的符号组合
        $signCombinations = self::generateSignCombinations(count($observed));
        
        foreach ($signCombinations as $signs) {
            $candidateStates = [];
            
            // 为每个观察值应用符号
            for ($i = 0; $i < count($observed); $i++) {
                if ($signs[$i] == '+') {
                    $candidateStates[] = $observed[$i];
                } else {
                    $candidateStates[] = -$observed[$i] & 0xffffffff;
                }
            }
            
            // 检查这些状态是否构成有效序列
            if (self::isValidSequence($candidateStates, $a, $b, $c)) {
                // 找到有效序列，预测下一个值
                $lastState = end($candidateStates);
                $nextState = self::xorshiftTransform($lastState, $a, $b, $c);
                $possibleStates[] = abs($nextState);
            }
        }
        
        return $possibleStates;
    }
    
    private static function xorshiftTransform($x, $a, $b, $c) {
        $x ^= $x << $a;
        $x ^= $x >> $b;
        $x ^= $x << $c;
        return $x & 0xffffffff;
    }
}

?>

2. 加固方案

<?php

/**
 * 加密安全的伪随机数生成器
 */
class SecureRNG {
    private $xorshift;
    private $counter;
    private $key;
    
    public function __construct($seed = null) {
        $seed = $seed ?? random_bytes(16);
        
        // 使用密码学安全种子初始化
        $this->key = hash('sha256', $seed, true);
        $this->counter = 0;
        
        // 使用Xorshift作为快速源
        $this->xorshift = new XorshiftFamily\Xorshift128(
            unpack('V', substr($this->key, 0, 4))[1]
        );
    }
    
    public function nextSecureInt(): int {
        $this->counter++;
        
        // 混合多个来源
        $xorshiftVal = $this->xorshift->nextInt();
        $hashInput = $this->key . pack('V', $this->counter);
        $hashVal = unpack('V', hash('sha256', $hashInput, true))[1];
        
        // 使用加密学安全的混合
        return ($xorshiftVal ^ $hashVal) & 0xffffffff;
    }
    
    public function nextSecureBytes($length): string {
        $result = '';
        while (strlen($result) < $length) {
            $result .= pack('V', $this->nextSecureInt());
        }
        return substr($result, 0, $length);
    }
}

?>

八、最佳实践总结

1. 选择指南

使用场景	推荐算法	理由
游戏随机数	Xorshift128+	速度快，分布好
模拟/科学计算	Xoroshiro128+	统计特性优秀
需要可重复性	任意Xorshift + 记录种子	确定性输出
密码学/安全	不要用Xorshift	使用CSPRNG

2. 实现建议

<?php

// 最佳实践示例
class BestPracticeRNG {
    private $rng;
    private $seed;
    
    public function __construct($seed = null) {
        // 1. 提供多种种子选项
        if ($seed === null) {
            $seed = mt_rand();
        } elseif (is_string($seed)) {
            $seed = crc32($seed);
        }
        
        $this->seed = $seed;
        
        // 2. 选择适当的算法
        $this->rng = new XorshiftFamily\Xorshift128($seed);
        
        // 3. 热身（避免初始状态相关问题）
        $this->warmUp();
    }
    
    private function warmUp() {
        for ($i = 0; $i < 10; $i++) {
            $this->rng->nextInt();
        }
    }
    
    // 4. 提供多种分布
    public function uniform($min = 0, $max = 1): float {
        return $min + ($this->rng->nextFloat() * ($max - $min));
    }
    
    public function normal($mean = 0, $stddev = 1): float {
        // Box-Muller变换
        $u1 = $this->uniform();
        $u2 = $this->uniform();
        
        $z0 = sqrt(-2.0 * log($u1)) * cos(2.0 * M_PI * $u2);
        return $mean + $z0 * $stddev;
    }
    
    // 5. 提供状态保存/恢复
    public function saveState(): array {
        return [
            'seed' => $this->seed,
            'rng_state' => $this->rng->getState(),
            'save_time' => time()
        ];
    }
}

?>

九、历史与发展

1. 发展历程

2003: George Marsaglia 发表Xorshift论文
2006: 发现参数 (13, 17, 5) 提供良好特性
2014: Sebastiano Vigna 提出Xoroshiro系列
2018: Xoshiro (旋转扩展) 进一步改进
2020: 广泛用于游戏引擎和模拟框架

2. 现代替代品

虽然Xorshift仍然优秀，但现代替代品包括：

• PCG (Permuted Congruential Generator)
• SplitMix64
• Threefry (并行随机数生成)

结论

Xorshift算法在性能和质量之间取得了极佳的平衡，使其成为非密码学应用的理想选择。其简单性、速度和良好特性使其在游戏开发、模拟和许多其他领域广受欢迎。

核心优势：

• 极快的速度（几个位操作）
• 可重复性（确定性输出）
• 长周期（2ⁿ-1）
• 易于实现和理解

主要限制：

• 不适用于密码学
• 某些变体存在统计缺陷
• 可能需要热身以避免初始状态问题

对于大多数应用来说，选择合适的Xorshift变体（如Xorshift128+或Xoroshiro128+）并提供适当的初始化和测试，将提供出色的随机数生成性能。