4

我需要在给定初始种子的情况下生成一个确定的（即可重复的）伪随机数序列，并从该序列中选择第 n 个项目。

如果 JavaScript 的随机函数是可播种的，我可以这样做：

function randomNth(seed, seq)
{
    var r;
    Math.randomSeed(seed);
    for (var i = 0; i++ < seq; i++)
    {
        r = Math.random();
    }
    return r;
}

然而，事实并非如此，替代的可播种 PRNG 看起来有点慢。要求第 250 个号码会很昂贵。

我认为哈希是我在这里想要的，可能类似于md5(seed + seq) % max但 JavaScript 没有 md5() ，如果我在代码中这样做，可能会有更好的哈希选择。

我想要一个函数

x = randomNth(seed, seq, maxVal) // x is int && x >= 0 && x < maxVal

或者，理想情况下

x = randomNth(seed, seq) // x >= 0 && x < 1, same as Math.random()

其他需求：

  • 必须在 node.js 和浏览器中运行
  • 数字应该在统计上是随机的（或足够接近，因为周期会很小）
  • 应该是 O(1) 并且性能合理
4

4 回答 4

3

此页面上有一些很好的 int -> int 散列函数，您可以使用其中之一。

function hash(a)
{
    a = (a+0x7ed55d16) + (a<<12);
    a = (a^0xc761c23c) ^ (a>>19);
    a = (a+0x165667b1) + (a<<5);
    a = (a+0xd3a2646c) ^ (a<<9);
    a = (a+0xfd7046c5) + (a<<3);
    a = (a^0xb55a4f09) ^ (a>>16);
    if( a < 0 ) a = 0xffffffff + a;
    return a;
}
var seed = 26254;
var index = 250;
alert( hash( seed + index ) );
于 2011-08-25T10:57:00.577 回答
2

最后，我使用了一位（非 SO）朋友的建议。我选择了 CRC32()，因为它速度非常快，并且给出了相当随机的值。

return crc32(seq + seed) % maxVal;

运行 800 万次后，maxVal = 8 的分布如下：

0 999998

1 999998

2 1000007

3 1000003

4 1000001

5 1000003

6 999992

7 999998

我还运行了 Hans 提到的 Donald Knuth 页面中提到的“ Marsaglia 著名的“Die Hard”测试电池，其结果在这里： CRC32() for random numbers Diehard results。简短的版本是它惨遭失败（对于如此少量的测试数据），但它仍然足以满足我在小范围内生成数字的需求。

于 2011-08-25T13:58:58.540 回答
1

在 javascript 中使用这个Mersenne Twister 实现。

于 2011-08-25T10:19:31.693 回答
1

Donald Knuth 可能会有所帮助：http ://www-cs-faculty.stanford.edu/~uno/news02.html#rng

于 2011-08-25T09:56:14.657 回答