4

我正在尝试在 JavaScript（glibc 中使用的那个）中创建一个自定义线性同余生成器（LCQ）。

它在维基百科上的属性是：m=2^31, a=1103515245, c=12345.

现在我得到下一个种子价值

x = (1103515245 * x + 12345) % 0x80000000 ; // (The same as &0x7fffffff)

虽然生成器似乎可以工作，但是当在画布上测试数字时：

cx = (x & 0x3fffffff) % canvasWidth; // Coordinate x (the same for cy)

他们似乎有可怕的偏见：http: //jsfiddle.net/7VmR9/3/show/

为什么会这样？通过选择不同的模数，视觉测试的结果看起来要好得多。

测试 JSFiddle 在这里：http: //jsfiddle.net/7VmR9/3/

更新

最后，我将转换固定为画布坐标，如下公式所示：

var cx = ((x & 0x3fffffff)/0x3fffffff*canvasWidth)|0

现在像素坐标不像使用模运算时那样畸形。

更新小提琴：http: //jsfiddle.net/7VmR9/14/

4

2 回答 2

4

对于生成器，公式是（您在第一部分忘记了模数）：

current = (multiplier * current * modul + addend) % modulus) / modulus

我意识到您尝试对其进行优化，因此我用它更新了小提琴，以便您可以将其用作优化的基础：

http://jsfiddle.net/AbdiasSoftware/7VmR9/12/

于 2013-07-13T02:30:17.247 回答
3

是的，看起来你解决了它。我也做过同样的事情。

线性同余生成器的形式为：

seed = (seed * factor + offset) % range;

但是，最重要的是，当从中获取实际随机数时，以下内容不起作用 ： 

random = seed % random_maximum;

这不起作用，因为第二个模数似乎抵消了生成器的影响。相反，您需要使用：

random = floor (seed / range * random_maximum);

（这将是一个随机整数；删除floor调用以获得随机浮点数。）

最后，我会警告你：在 JavaScript 中，当处理超过 dword 限制的数字时，会损失精度。因此，您的 LCG 的随机结果可能是随机的，但它们很可能与用 C++ 或其他实际支持双字数学的低级语言实现的相同 LCG 的结果不匹配。

同样由于不精确，LCG的周期极易被大大缩短。因此，例如，您引用的 glibc LCG 的循环可能是 40 亿（也就是说，它会在重新开始并重新生成完全相同的一组数字之前生成超过 40 亿个随机数）。这个 JavaScript 实现可能只会得到 10 亿，或者可能更少，因为当乘以因子时，这个数字超过了 40 亿，并且这样做会失去精度。

于 2014-04-28T16:50:22.887 回答