C++ 从零实现高质量随机数生成器

本项目选择：Xorshift + 教学友好设计

3.3 Xorshift 算法原理

Xorshift 是 George Marsaglia 提出的一类随机数生成算法，其核心思想是：

使用异或（XOR）与位移（Shift）操作构造长周期随机序列

以 Xorshift64 为例：

x ^= x << 13; x ^= x >> 7; x ^= x << 17;

特点：

• 运算极快
• 周期长（2^64 - 1）
• 实现简单
• 非密码学安全（适合数值模拟）

四、实现思路

4.1 架构设计

RandomEngine
├─ nextUint64() → 核心随机数
├─ uniform01() → [0,1)
├─ uniform(a,b) → 均匀分布
├─ normal(mean,σ) → 正态分布
└─ exponential(λ) → 指数分布

4.2 分布生成策略

1. 均匀分布：直接映射
2. 正态分布：Box–Muller 变换
3. 指数分布：反函数法

4.3 可复现性设计

• 所有随机数只依赖：
  • 当前状态
  • 固定 seed
• 不使用系统时间作为默认种子

五、完整实现代码

/******************************************************
 * File: random_engine.h
 * Description: 随机数生成器接口
 ******************************************************/
#ifndef RANDOM_ENGINE_H
#define RANDOM_ENGINE_H
#include <cstdint>

class RandomEngine {
public:
    explicit RandomEngine(uint64_t seed = 88172645463325252ull);
    uint64_t nextUint64();
    double uniform01();
    double uniform(double a, double b);
    double normal(double mean = 0.0, double stddev = 1.0);
    double exponential(double lambda);
private:
    uint64_t state;
    bool hasSpare;
    double spare;
};
#endif

/******************************************************
 * File: random_engine.cpp
 * Description: Xorshift 随机数生成器实现
 ******************************************************/
#include "random_engine.h"
#include <cmath>
#include <stdexcept>

/* 构造函数：初始化种子 */
RandomEngine::RandomEngine(uint64_t seed) : state(seed), hasSpare(false) {
    if (state == 0) state = 88172645463325252ull;
}

/* 核心 Xorshift64 算法 */
uint64_t RandomEngine::nextUint64() {
    uint64_t x = state;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    state = x;
    return x;
}

/* 生成 [0,1) 上均匀分布 */
double RandomEngine::uniform01() {
    return (nextUint64() >> 11) * (1.0 / 9007199254740992.0);
}

/* 生成 [a,b) 上均匀分布 */
double RandomEngine::uniform(double a, double b) {
    if (a >= b) throw std::invalid_argument("uniform: a must be < b");
    return a + (b - a) * uniform01();
}

/* 正态分布：Box–Muller 变换 */
double RandomEngine::normal(double mean, double stddev) {
    if (stddev <= 0.0) throw std::invalid_argument("normal: stddev must be positive");
    if (hasSpare) {
        hasSpare = false;
        return mean + stddev * spare;
    }
    double u, v, s;
    do {
        u = uniform(-1.0, 1.0);
        v = uniform(-1.0, 1.0);
        s = u * u + v * v;
    } while (s >= 1.0 || s == 0.0);
    s = std::sqrt(-2.0 * std::log(s) / s);
    spare = v * s;
    hasSpare = true;
    return mean + stddev * (u * s);
}

/* 指数分布 */
double RandomEngine::exponential(double lambda) {
    if (lambda <= 0.0) throw std::invalid_argument("exponential: lambda must be positive");
    return -std::log(1.0 - uniform01()) / lambda;
}

/******************************************************
 * File: main.cpp
 * Description: 示例与测试
 ******************************************************/
#include <iostream>
#include "random_engine.h"

int main() {
    RandomEngine rng(12345);
    std::cout << "Uniform [0,1):\n";
    for (int i = 0; i < 5; ++i) std::cout << rng.uniform01() << std::endl;
    std::cout << "\nNormal(0,1):\n";
    for (int i = 0; i < 5; ++i) std::cout << rng.normal() << std::endl;
    std::cout << "\nExponential(lambda=2):\n";
    for (int i = 0; i < 5; ++i) std::cout << rng.exponential(2.0) << std::endl;
    return 0;
}

六、代码解读

6.1 nextUint64

• 核心随机数生成函数
• 实现 Xorshift64 算法
• 提供高质量基础随机序列

6.2 uniform01

• 将整数随机数映射到 [0,1)
• 保证浮点精度均匀性

6.3 normal

• 使用 Box–Muller 变换
• 一次生成两个正态随机数
• 提高性能，减少计算量

6.4 exponential

• 使用反函数法
• 基于均匀分布构造指数分布

七、总结

通过本项目，我们：

1. 从数学与工程角度理解了 RNG 原理
2. 实现了一个高性能、可复现的随机数引擎
3. 构建了多个常用概率分布
4. 为统计分布与 Monte Carlo 提供了基础组件

该随机数生成器：

• 比 rand() 更可靠
• 比标准库更透明
• 非常适合教学与科研

八、常见问题及解答

Q1：是否适合密码学？

A：不适合，需要使用 CSPRNG（如 AES-CTR）。

Q2：是否线程安全？

A：当前版本不是，可通过线程私有实例解决。

Q3：周期有多长？

A：Xorshift64 周期为 2^64 - 1。

九、扩展方向与性能优化

1. 替换为 PCG / Xoshiro
2. 支持并行随机数流
3. 增加更多统计分布
4. SIMD 批量生成
5. 封装为完整 C++ 数值与统计库