为什么在兰特使用1103515245?
我正在谈论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
)应该只满足2个条件:
-
a - 1
可被m
所有素因子整除。
(在我们的例子中,m = 2^32
,int的大小,所以m
只有一个素因子= 2) - 如果
m
是4的倍数,则a - 1
是4的倍数。
(32768是4的倍数,也是1103515244)
为什么他们选择了这样一个奇怪的,难以记住的,“男人,我厌倦了这些随机数字,写下任何”数字,如1103515245?
也许有一些明智的理由,这个数字在某种程度上比另一个更好?
例如,为什么不设置a = 20000000001
? 它更大,更酷,更容易记住。
如果使用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架飞机制作了“随机”情节,他的计算机中心的编程顾问告诉他,他滥用了随机数发生器:“我们保证每个数字都是随机的,但我们不是保证他们中的一个以上是随机的。“这使我们的研究生教育至少延迟了一年!
请记住, rand()
是均匀分布的近似值。 使用这些数字是因为它们经过测试表明它们可以产生更加统一的分布。
鉴于可表示范围内的大量无符号整数对,我怀疑是否有人用所有有效种子尝试了所有这些整数。 如果您认为您有更好的参数选择,那就试一试吧! 您有代码,只需分解LCG的参数并运行测试。 生成一堆数字(比如1000万),计算生成数字的直方图并绘制出来以查看分布。
编辑如果您对开发用于实际应用的伪随机数生成器感兴趣,我建议您阅读有关该主题的大量文献。 上面给出的“建议”仅建议帮助表明选择任意“更大,更酷,更容易记住”的LCG参数将导致非常差的分布。 /编辑
此外,它是一个库函数,我从未见过使用标准库版本的rand()
来记住它的LCG参数的程序。
早期计算往往关注位和字节,并与寄存器一起使用以最小化代码字节(在行有字节之前)
我只在下面找到了一条合理的线索:
这个发生器的输出不是很随机。 如果我们使用上面列出的样本生成器,那么16个关键字节的序列将是高度非随机的。 例如,事实certificaterand()的每个连续输出的低位将交替(例如,0,1,0,1,0,1,…)。 你知道为什么吗? x * 1103515245的低位与x的低位相同,然后添加12345只是翻转低位。 因此低位交替。 这将可能的键集缩小到仅2113种可能性;远低于期望值2128。
http://inst.eecs.berkeley.edu/~cs161/fa08/Notes/random.pdf
还有两个合理的答案:
由Bays,Durham Bays,Carter,SD Durham改进一个糟糕的随机数发生器(1976)
这个数字似乎很特别,它只是在两个素数之间:P。
现在认真谈论,看看它是否是一个好的选择,只需看看输出。 即使翻转一位,您也应该看到非常不同的结果。
另外,考虑一下你期望的可预测性……实施是可怕的,你可以考虑一个更强大而简单的替代方案,如FNV-1a 。