algorithm - 从线性同余 RNG 生成随机向量

Question

如果我有一个线性同余生成器，这样每次给定一个特定的种子，我就可以确切地知道我们可以生成一个固定的伪随机数序列，这些序列已知均匀分布在 [1, K] 之间，我应该如何使用这样的一个RNG来生成一个均匀分布在[1, K^M]之间的M维随机向量？

Answer 1

如果您对除了 M 维情况之外的所有 LCG 都满意，那么最基本的解决方案是为 M 个单独的生成器使用 M 个单独的种子。这至少可以确保给定向量的元素是独立的（在播种算法的限制内）。

但是，您可能真正想要的是一个状态至少为M*log_2(K)位的 PRNG，它可以保证向量的所有部分之间有一些混合。如果这超过 64 位，那么为此使用 LCG 似乎需要付出很多努力来实现比许多更简单的解决方案更弱的东西。

如果 M 是常数并且不是不合理的大，那么您可能会查看 xorshift、multiply-with-carry 或 WELL。否则，您可能会坚持使用著名的大周期生成器或密码算法，而对理论限制视而不见。

Answer 2

我不知道你打算使用什么编程语言或者K和M的范围是多少，但是如果K是2的幂，你可以简单地附加M个伪随机数的二进制表示来统一得到一个伪随机数分布在 [1, K^M] 上。如果 K 不是 2 的幂，您可以使用某种分区函数或重新滚动某些值来构造 [1, K^M] 分布数字的位。