定制随机数生成器

Question

有没有可能获得一个极快但可靠的（相同输入=相同输出，所以我不能使用时间）伪随机数生成器？我希望最终结果类似于float NumGen（int x，int y，int seed）;，以便基于这三个值创建0到1之间的随机数。我找到了几个随机数生成器，但无法让它们工作，并且Unity附带的随机数生成器太慢了。我必须每1米地形调用大约9次生成器，因此我并不介意它不完全是统计随机的，只要它能够非常快速地工作即可。有人知道符合我的需求的算法吗？谢谢 :)

- Nicholas Pipitone

---

是的，这是可能的。一个线性同余生成器只需两行代码。 - undefined

我会查看System.Random生成器。虽然它使用时间，但如果你用你的种子替换那个时间，甚至将两者结合起来，你就能得到你在这里描述的东西。 - undefined

@EricLippert 我找不到一种方法来实现一个线性同余生成器，以接受3个输入并仍然在0f-1f范围内工作。 - undefined

@WoutervanderHouven 这就是我一直在使用的，但是我每秒钟调用该函数数百次，所以它们使用的复杂算法对资源要求很高。 - undefined

明白了。所以仅仅生成一个包含10000个随机数的序列是不够的。另外一个复杂性在于，你将会为(100, 200)、(100, 201)、(99, 200)等生成数字；坐标并没有增加任何熵。我目前还不知道有没有符合你要求的算法，但我会考虑一下。 - undefined

Answer 1

我认为你低估了System.Random类。它非常快速。我相信你的减速与在每次调用NumGen方法时创建新的Random类实例有关。

在我的快速测试中，我能够使用System.Random生成约100,000个随机数，大约需要1毫秒。

要避免减速，请考虑2D平面中的种子点。分散种子点，使它们覆盖的距离不超过100,000米。然后将（或计算）与每米最近的种子点相关联，并将该点用作System.Random的种子。

是的，你将生成大量永远不会使用的随机数，但它们几乎是免费的。

伪代码：

double NumGen(x, y, distance, seed) {
  Random random = new Random(seed);
  double result = 0;
  for (int i=0; i<distance; i++) {
    result = random.NextDouble();
  }
}

您可以修改此简单的概述，以返回一系列随机数字（可能表示网格），并将其与缓存机制相结合。这样可以节省内存并减少 CPU 消耗。

- Sam Axe

---

如果您只有一个实例（或几个实例）的Random类，性能将会非常好，这显然取决于您用于测量的变量。 - undefined

Answer 2

我猜你在每次调用NumGen时都需要创建一个Random实例。为了让函数对于相同的参数返回相同的数字，你可以使用哈希函数。

我测试了一些东西，这段代码比重新创建Random实例快了大约3倍。

//System.Security.Cryptography
static MD5 hasher = MD5.Create();
static byte[] outbuf;
static byte[] inbuf = new byte[12];
static float floatHash(uint x, uint y, uint z) {
    inbuf[0]= (byte)(x >> 24);
    inbuf[1]=(byte)(x >> 16);
    inbuf[2]=(byte)(x >> 8);
    inbuf[3]=(byte)(x);
    inbuf[4]=(byte)(y >> 24);
    inbuf[5]=(byte)(y >> 16);
    inbuf[6]=(byte)(y >> 8);
    inbuf[7]=(byte)(y);
    inbuf[8]=(byte)(z >> 24);
    inbuf[9]=(byte)(z >> 16);
    inbuf[10]=(byte)(z >> 8);
    inbuf[11]=(byte)(z);
    outbuf = hasher.ComputeHash(inbuf);
    return ((float)BitConverter.ToUInt64(outbuf, 0))/ulong.MaxValue;
}

使用一些RSA方法的另一种方法比new System.Random(seed)快约5倍：

static uint prime = 4294967291;
static uint ord = 4294967290;
static uint generator = 4294967279;
static uint sy;
static uint xs;
static uint xy;
static float getFloat(uint x, uint y, uint seed) {
    //will return values 1=> x >0; replace 'ord' with 'prime' to get 1> x >0
    //one call to modPow would be enough if all data fits into an ulong
    sy = modPow(generator, (((ulong)seed) << 32) + (ulong)y, prime);
    xs = modPow(generator, (((ulong)x) << 32) + (ulong)seed, prime);
    xy = modPow(generator, (((ulong)sy) << 32) + (ulong)xy, prime);
    return ((float)xy) / ord;
}
static ulong b;
static ulong ret;
static uint modPow(uint bb, ulong e, uint m) {
    b = bb;
    ret = 1;
    while (e > 0) {
        if (e % 2 == 1) {
            ret = (ret * b) % m;
        }
        e = e >> 1;
        b = (b * b) % m;
    }
    return (uint)ret;
}

我进行了一项测试，生成了100000个浮点数。我使用索引作为System.Random的种子，并将其作为floatHash的x参数（y和z都为0）。

System.Random：最小值：2.921559E-06 最大值：0.9999979 重复次数：0

floatHash MD5：最小值：7.011156E-06 最大值：0.9999931 重复次数：210（两个值返回了两次）

getFloat RSA：最小值：1.547858E-06 最大值：0.9999989 重复次数：190

- schwer

---

你确定输出是随机的吗？我只看到你在对字节数组进行哈希，并将结果除以ulong.maxvalue。这样怎么可能是随机的呢？ - undefined

它并不是完全随机的。我将一个测试报告编辑成了答案。 - undefined

这看起来很完美，但我在使用它时遇到了麻烦。我正在使用Unity，但不知何故每次尝试运行它时都会崩溃。我认为它不喜欢无符号整数（uint），因为我之前尝试过处理它们，而那花费了很长时间。有没有办法将其转换为仅使用整数（int），因为我不确定代码的工作原理，而且按位运算符似乎依赖于位长度。 - undefined

@NicholasPipitone 我修改了代码。现在所有的整数都是无符号的。之前由于将负整数转换为ulong导致了整数溢出问题。 - undefined