为什么在兰特使用1103515245？

Question

我在谈论C标准的这个令人惊讶的简单实现rand():

static unsigned long int next = 1;

int rand(void)  /* RAND_MAX assumed to be 32767. */
{
    next = next * 1103515245 + 12345;
    return (unsigned)(next/65536) % 32768;
}

从这篇维基百科文章中我们知道乘数a(在上面的代码中a = 1103515245)应该只满足两个条件:

1. a - 1被所有主要因素整除m.
   (在我们的例子中m = 2^32,int的大小,所以m只有一个素因子= 2)
2. a - 1是4的倍数,如果m是4 的倍数.
   (32768是4的倍数,也是1103515244)

为什么他们选择了这样一个奇怪的,难以记住的,"男人,我厌倦了这些随机数字,写下任何"数字,如1103515245？

也许有一些明智的理由,这个数字在某种程度上比另一个更好？

例如,为什么不设置a = 20000000001？它更大,更酷,更容易记住.

Answer 1

如果使用LCG在d维空间上绘制点,它们将位于最多(d!m)^1/_d超平面上.这是LCG的已知缺陷.

如果你没有仔细选择a和m(超出完全周期性的条件),它们可能位于比这更少的平面上.这些数字已经通过所谓的光谱测试来选择.

"光谱测试"(名称来自数论)是连续超平面之间的最大距离,其中d维关节分布位于其上.您希望它尽可能小,因为您可以测试尽可能多的d.

有关该主题的历史回顾,请参阅此文章.请注意,您引用的生成器在文章中提到(作为ANSIC)并且确定不是很好.然而,高阶16位是可接受的,但是许多应用程序将需要超过32768个不同的值(正如您在评论中指出的那样,周期确实是2 ^ 31--维基百科链接中完整周期性的条件可能只是必要的).

在ANSI文件中的原始源代码没有采取高位16位,产生一个非常贫穷的发生器,它是容易误操作(rand() % n是什么人首先想到的画之间的数字0和n,这产生了一些非常非随机的这个案例).

另见数值配方中关于LCG的讨论.引用:

更糟糕的是,许多早期的发电机碰巧对m和a做出了特别糟糕的选择.一个臭名昭着的例行程序,RANDU,a = 65539和m = 231,在IBM大型计算机上广泛使用多年,并被广泛复制到其他系统上.我们其中一人回忆说,作为一名研究生,只有11架飞机制作了"随机"情节,他的计算机中心编程顾问告诉他,他滥用了随机数发生器:"我们保证每个数字都是随机的,但我们不是保证他们中的一个以上是随机的."这使我们的研究生教育至少延迟了一年!

Answer 2

请记住,这rand()是均匀分布的近似值.使用这些数字是因为它们经过测试表明它们可以产生更加统一的分布.

鉴于可表示范围内的大量无符号整数对,我怀疑是否有人用所有有效种子尝试了所有这些整数.如果您认为您有更好的参数选择,那就试一试吧!您有代码,只需分解LCG的参数并运行测试.生成一堆数字(比如1000万),计算生成数字的直方图并绘制以查看分布.

编辑 如果您对开发用于实际应用的伪随机数生成器感兴趣,我建议您阅读有关该主题的大量文献.上面给出的"建议"仅建议帮助表明选择​​任意"更大,更酷,更容易记住"的LCG参数将导致非常差的分布. /编辑

此外,它是一个库函数,我从未见过使用标准库版本rand()来记住其LCG参数的程序.