random - 寻找算法源

Question

翻阅我的 3 卷 TAOCP，我找不到短随机序列的来源：

// Seed always in 1..0x10000
Seed = (Seed * const) % 0x10001

还有一个算法，可能还有一个 MIX 程序来验证 const 以便返回所有 2^16 值。至少那是我记得的。同样在相同的一般领域中，上述递归有效，因为 (2^16)+1 是素数，但可惜 (2^32)+1 和 (2^64)-1 都不是素数。

FWIW，将 const 替换为 iconst = 1/const (mod 0x10001) 以相反的顺序生成序列。即 const*iconst%0x10001 = 1

Answer 1

该算法是线性同余生成器(LCG) 的变体，称为素模乘法线性同余生成器 (PMMLCG - 参见 Law 的“Simulation Modeling and Analysis, 5e” p.400)，有时也称为Lehmer 生成器。我提供的两个链接都给出了通用参数化，第一个链接给出了选择参数的规则，这将给出一个完整的循环。然而，拥有完整的周期并不是拥有一个好的生成器的充分条件，正如 IBM 在现在臭名昭著的RANDU中毁灭性地发现的那样。

我强烈建议您只使用经过充分测试的算法，要做到这一点非常困难。有一些经过充分研究且现成可用的算法现在可以广泛使用，它们比任何 LCG 都要好得多。