1

我对rand(x, y, seed)基于其参数返回（伪）随机数的函数感兴趣，该函数具有以下属性：

  1. 返回的值应该取决于它的 3 个参数，而不是取决于rand到目前为止被调用的次数。例如，假设这些调用，按以下顺序：

    rand(0, 0, 123) = 1
rand(0, 1, 123) = 2
rand(0, 2, 123) = 3

    然后rand用相同的参数调用，但顺序不同，我们应该得到相同的值。例如：

    rand(0, 1, 123) = 2
rand(0, 2, 123) = 3
rand(0, 0, 123) = 1

  2. 该函数应该具有良好的通常属性（体面，我真的不需要任何非常花哨的东西）PRNG：大周期，均匀分布等。返回适合有符号整数的正整数很好。如果你愿意，它也可以更高。

  3. 假设这些数字将用于生成矩阵。然后更改种子应确保生成的矩阵看起来与其他种子生成的矩阵尽可能不同。这应该发生在尽可能多的种子上：我不希望矩阵重复。

如果有帮助，我的种子将始终是以毫秒为单位的 unix 时间戳（如果这以某种方式使其更容易，也可以以秒为单位）。所有参数都可以高达 32 位有符号整数，但在函数内部使用 64 位值不是问题。

我可以为此使用什么功能？

我想到的：

Perlin 噪声似乎做了我想做的一些事情，但我不知道它作为 PRNG 到底有多合适，尤其是在分布方面。我也不确定它的效率如何，因为我的(x, y)参数将是相当随机的，我无法为所有参数预先计算它。

我还研究了以下功能：

p = 1400328593
rand(x, y, seed) = (x * x * seed + y * seed * seed + seed * x * y + seed) mod p
                 = (seed * (x * x + y * seed + x * y + 1)) mod p

这似乎产生了足够好的数字。根据我的（非常弱的）测试，它们似乎也分布得很好。测试这个时期虽然更难，但我没有这样做。

更新：

这是上述函数的Enttime(NULL)的输出，其中in C 作为它的种子和为 生成的值(x, y) in {0 ... 999} x {0 ... 999}：

熵 = 每字节 3.312850 位。

最佳压缩将使这个 9207076 字节文件的大小减少 58%。

9207076 个样本的卡方分布为 229710872.43，并且随机超过该值的次数不到 0.01%。

数据字节的算术平均值为 52.3354（127.5 = 随机）。Pi 的 Monte Carlo 值为 4.000000000（误差 27.32%）。序列相关系数为 0.036131（完全不相关 = 0.0）。

这在实践中是否足够好（理论上，上述测试表明它根本不好），还是我应该使用一些众所周知的东西？

4

2 回答 2

2

听起来你想要一个哈希函数。如果不是太低效，请选择安全的，例如 SHA1，因为它保证具有良好的分布特性；否则，您可以使用常见的哈希函数，例如 FNV。只需使用您的种子和坐标作为输入数据，并将哈希值作为随机值。

于 2012-10-02T10:32:36.463 回答
1

您可以尝试使用Blum Blum Shub。它具有您可以直接计算系列的第 n 个值的属性，这似乎适合您的情况。它需要三个参数，p、q 和 x0。p 和 q 是素数，x0 是 p 和 q 的素数。因此，您的参数 x 和 y 可用于查找第 x 和第 y 素数，然后它们将适用于 p 和 q，然后您可以使用第三个参数为 x0 找到合适的值。这有点乏味，而且 Blum Blum Shub 很慢，因为它是一个加密的 RNG，但如果你真的不需要速度，那么它会工作并且不会很难实现。

另一种方法是使用像CMWC这样的 RNG ，并用 x + y^i + seed^(2i) 之类的东西填充生成器的第 i 个位置，运行生成器一会儿（可能是一些乘以它存储的值的数量），然后从中提取一个值。

如果您想使用 CMWC，您可以在此处查看我在 github 上的实现，以及在此处构建具有已知周期的生成器的值。

于 2012-10-01T16:58:42.167 回答