前不久重看银河系漫游指南的产生一个困惑,为什么计算机最终得出的人和宇宙生命之类的终极答案是42?这个数字有什么特别的?难道就因为它紧紧挨着Visual C的Rand()函数产生的第一个随机数41?那为什么又是41?
于是为了探究宇宙和人类的本源,我开始考据为什么Rand()函数产生的第一个随机数是41这个究极问题。
本着科学严谨的精神,我采用了最严肃的考据方式。 百度之。
未果。
尼玛那么奇妙的问题居然没有人解答!!
好吧,那我去编译器看一下源代码好了。如你所知,调用rand函数必须包含stdlib头,那么rand的实现毫无疑问就在stdlib.c的文件里面。可是,哪位英雄能告诉我怎么查看stdlib.c啊??
于是又未果。
自我落草为人以来从没有那么沮丧过。于是百度。
以下这个LCG算法就是大名鼎鼎的线性同余法,传说是最简单最朴素的的伪随机数产生算法。
LCG 算法数学上基于公式:
X(n+1) = (a * X(n) + c) % m //果1.
其中,各系数为:
模m, m > 0
系数a, 0 < a < m
增量c, 0 <= c < m
原始值(种子) 0 <= X(0) < m
其中参数c, m, a比较敏感,或者说直接影响了伪随机数产生的质量。
分析公式不难发现,a,m,c和都是确定的参数,X(n)为种子数,X(n+1)就是产生的伪随机数了。
百度又说Visual C的初始种子为1,即X(0)=1,a=214013, c=2531011,m=2^32
于是我又一次本着严谨的科学态度把种子数和各参数带入公式,得出的结果2745024显然和宇宙的终极答案无关!
又一次沮丧于是百度。
int __cdecl rand ( void )
{
#ifdef _MT
_ptiddata ptd = _getptd();
return( ((ptd->_holdrand = ptd->_holdrand * 214013L
+ 2531011L) >> 16) & 0x7fff );
#else /* _MT */
return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
#endif /* _MT */
}
相信一些编程功底稍强的同学看到这里就已经恍然大悟并且萌生了这个SB折腾那么久早点把代码贴出来不就好了这么自然而又合理的想法。可是为了照顾象我这样看到#和>>就头疼的小白不得不把程序再翻译一下。种子值的递推式是:seed = seed *214013L+2531011L //此处L的意思是该数位Long型,应该有警告编译器不要擅自优化的内涵返回值和种子值的关系是:return = (seed>>16) & 0x7fff即取seed的高16位后与7fff(16进制)=0111 1111 1111 1111(2进制)=32767(十进制)与一把
2745024=(1*214013+2531011)mod 2^32。看这个数字的高16位。0*8 +0010 1001 ,换算一下果然就是十进制的41耶!
至此,宇宙的的最终答案已经得到了解决。但是,本着严谨的科学态度,我们要经行下一步验证。
把41作为种子数带入,(41*214013+2531011)mod 2^32
其高16位显然不是我们熟悉的第二个伪随机数18467(10进制)= 0100 1000 0010 0011(2进制)
宇宙果然不是那么简单的..
换个思路,把处理之前的RAW(即右移取与之前的数)(2745024*214013+2531011)mod 2^32
将其高16位与0X7fff取与后即可得18467(10进制)= 0100 1000 0010 0011(2进制)。
经过后续实验发现,种子数取为运算后的二进制数的低32位,高位抛弃。
至此,宇宙的本源之谜彻底告破。
附1.
Visual C中Rand函数产生的前六个随机数
41
18467
6334
26500
19169
15724
之所以都没有超过32767是因为只取了16位,在stdlib.h里由宏RAND_MAX所控制。
附2.
部分编译器使用的各个参数值:
Source | m | a | c | rand() / Random(L)的种子位 |
Numerical Recipes | 2^32 | 1664525 | 1013904223 | |
Borland C/C++ | 2^32 | 22695477 | 1 | 位30..16 in rand(), 30..0 in lrand() |
glibc (used by GCC) | 2^32 | 1103515245 | 12345 | 位30..0 |
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ | 2^32 | 1103515245 | 12345 | 位30..16 |
Borland Delphi, Virtual Pascal | 2^32 | 134775813 | 1 | 位63..32 of (seed * L) |
Microsoft Visual/Quick C/C++ | 2^32 | 214013 | 2531011 | 位30..16 |
Apple CarbonLib | 2^31-1 | 16807 | 0 | 见Park–Miller随机数发生器 |
参考:
2.算法驿站的博客
PS:电影中计算机算出42是因为天文学家在研究和测量银河系总重量的时候,发现答案竟然与42相呼应。这个答案是3 X 10^4千克,也就是3后面42个零。这似乎很深奥,但对天文学家来说知道银河系所有物质的总重量是解决暗物质问题的关键,据估计暗物质占据了96%的宇宙空间。 红色部分来自百度知道。