Show HN: LoopMix128 – 快速 C 语言 PRNG (0.46ns)，2^128 周期，通过 BigCrush/PractRand 测试
LoopMix128 是一个用 C 语言编写的快速伪随机数生成器 (PRNG)，具有 2^128 的周期。它通过了 BigCrush 和 PractRand (32TB) 测试，表明其统计质量良好。该 PRNG 性能优异，速度快于标准库和其他现代高速 PRNG。文章还介绍了其算法细节、并行流实现方法，以及与其他 PRNG 在 PractRand 测试中的对比结果。
[正文内容]
danielcota/LoopMix128
一个非常快速的 64 位 PRNG，具有 2^128 周期，已验证注入性，通过了 BigCrush 和 PractRand (32TB) 测试。
License
25 stars 1 fork Branches Tags Activity
LoopMix128：快速且健壮的 2^128 周期 PRNG
该仓库包含 LoopMix128，一种速度极快的伪随机数生成器 (PRNG)，保证周期为 2^128，经过验证的注入性，并且在 BigCrush 和 PractRand (32TB) 中都干净地通过了测试。 它专为速度和统计质量都很重要的非加密应用程序而设计。
特性
- 高性能： 比标准库生成器快得多，并且与其他现代高速 PRNG（如 wyrand 和 xoroshiro128++）相比具有竞争力或更快。
- 良好的统计质量： 已通过 TestU01 的 BigCrush 套件和 PractRand（高达 32TB），且没有异常。
- 2^128 周期： 通过其 128 位 low/high 计数器循环的最小周期长度为 2^128。
- 已验证的注入性： Z3 Prover 验证了其 192 位状态的注入性。（z3 script） （results）
- 并行流： 注入性的 192 位状态有助于如下所述的并行流。
性能
- 速度： 比 Java random 快 8.75 倍，比 Java xoroshiro128++ 快 21%，比 C xoroshiro128++ 和 PCG64 快 98%。（benchmark）
- 通过了 256M 到 32TB 的 PractRand 测试，没有异常。（results）
- 通过了 BigCrush 测试，具有以下最低 p 值：（results）
0.01sknuth_MaxOft (N=20, n=10000000, r=0, d=100000, t=32), Sum ChiSqr0.02sknuth_CouponCollector (N=1, n=200000000, r=27, d=8), ChiSqr0.02svaria_WeightDistrib (N=1, n=20000000, r=28, k=256, Alpha=0, Beta=0.25), ChiSqr
算法细节
// Golden ratio fractional part * 2^64
const uint64_t GR = 0x9e3779b97f4a7c15ULL;
// Initialized to non-zero with SplitMix64 (or equivalent)
uint64_t slow_loop, fast_loop, mix;
// Helper for rotation
static inline uint64_t rotateLeft(const uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}
// --- LoopMix128 ---
uint64_t loopMix128() {
uint64_t output = GR * (mix + fast_loop);
// slow_loop acts as a looping high counter (updating once per 2^64 calls) to ensure a 2^128 period
if ( fast_loop == 0 ) {
slow_loop += GR;
mix ^= slow_loop;
}
// A persistent non-linear mix that does not affect the period of fast_loop and slow_loop
mix = rotateLeft(mix, 59) + fast_loop;
// fast_loop loops over a period of 2^64
fast_loop = rotateLeft(fast_loop, 47) + GR;
return output;
}
（注意：上面的代码显示了核心逻辑。有关完整的 seeding 和用法示例，请参见实现文件。）
并行流
由于 LoopMix128 的 192 位状态经过验证的注入性，因此可以按以下方式实现并行流：
- 只需随机 seeding fast_loop、slow_loop 和 mix，并利用大的 2^192 注入状态，这使得冲突的可能性极低。
- 或者，如果绝对关键 - 为每个流随机 seeding fast_loop 和 mix，并手动为每个流唯一分配 slow_loop，同时考虑到 slow_loop 通常在每个 2^64 周期结束时增加 GR（均匀间隔跨流的 slow_loop）。
PractRand 测试（使用不同的种子）
由于运行 BigCrush 和 PractRand 的行为可能会因初始 seeding 状态而异，因此还使用不同的初始种子（使用 SplitMix64 进行 seeding）多次从 256M 运行到 8GB PractRand。 以下是在 LoopMix128 和一些参考 PRNG 运行 1000 次 PractRand 时可疑结果的总数：
LoopMix128 0 failures, 24 suspicious
xoroshiro256++ 0 failures, 27 suspicious
xoroshiro128++ 0 failures, 28 suspicious
wyrand 0 failures, 32 suspicious
/dev/urandom 0 failures, 37 suspicious
创建
由 Daniel Cota 在偶然的情况下陷入 PRNG 兔子洞之后创建。
关于
一个非常快速的 64 位 PRNG，具有 2^128 周期，已验证注入性，通过了 BigCrush 和 PractRand (32TB) 测试。
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published