JavaScript 伪随机序列生成器

Question

JavaScript 伪随机序列生成器

5

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

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

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

然而，并没有替代方案，可种子的伪随机数生成器看起来有点慢；要求第250个数字会很昂贵。我认为这里需要哈希，也许像md5(seed + seq) % max这样的东西，但JavaScript没有md5()，如果我在代码中执行它，可能会有更好的哈希选择。我想要一个函数，其中x = randomNth(seed, seq, maxVal) // x是int && x >= 0 && x < maxVal，或者理想情况下，x = randomNth(seed, seq) // x >= 0 && x < 1，与Math.random()相同。其他要求：必须在node.js和浏览器中运行，数字应该是统计随机的（或者接近于小周期），应该是O(1)并且性能合理。

- Deebster

1

只是一些有关编程的随机内容 :) 随机性 - Bakudan

4个回答

3

最终我采用了一位（非SO）朋友的建议。我选择了CRC32()，因为它非常快，并且可以提供相当随机的值。

返回crc32(seq + seed) % maxVal;

对于maxVal = 8，连续运行800万次产生了以下分布：

0 999998

1 999998

2 1000007

3 1000003

4 1000001

5 1000003

6 999992

7 999998

我还运行了Donald Knuth页面Hans提到的Marsaglia's famous "Die Hard" battery of tests，结果在这里：用于随机数Diehard结果的CRC32()。简单来说，它在测试数据很少的情况下失败了（失败得很惨），但对于我在生成小范围内的数字时仍然足够好。

- Deebster

1

FYI，第一个链接已经失效了，也许可以用https://en.wikipedia.org/wiki/Diehard_tests来替换它。 - Maxime Pacary

1

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

- HBP

1

使用这个JavaScript中的Mersenne Twister实现。

- nobody

但是我如何得到第250个数字呢？播种并运行250次吗？ - Deebster

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nobody · Accepted Answer

这个页面上有一些好的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 ) );