algorithm - 参数相关的 PRNG

Question

我对函数 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 noise似乎做了我想做的一些事情，但我不知道它作为 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

这似乎 生成了足够好的数字。根据我的(非常弱的)测试，它们似乎也分布得很好。虽然测试这段时间比较困难，但我还没有这样做。

更新:

这是 Ent 的输出对于上述函数，以 C 中的 time(NULL) 作为其种子，并为 {0 ... 999} x {0 ... 999} 中的 (x, y) 生成值:

Entropy = 3.312850 bits per byte.

Optimum compression would reduce the size of this 9207076 byte file by 58 percent.

Chi square distribution for 9207076 samples is 229710872.43, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 52.3354 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is 0.036131 (totally uncorrelated = 0.0).

这在实践中是否足够好(理论上，上述测试表明它一点也不好)，或者是否有我应该使用的众所周知的东西？

Answer 1

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