随机函数random(n)实现

rand()随机函数实现原理

关于“随机数”的产生有许多算法，但无论如何，都不可能产生真正的随机数，因为电脑程序是个确定状态转换机，一种输入必定产生一种确定的输出。           但要实现“不可预知”还是可以做到的，只需有“不可预知”的输入或者初始化就可以了，像系统时间，网络实时带宽，Cpu使用率等等都可以作为“不可预知”的量来初始化随机函数。

产生整数rand的原理是：           y＝ax＋b（mod   n）其中，n一般是一个很大的素数，几万。    a也是大素数。而且a，b，n都是常数。所以rand的产生决定于x，他被称为seed。           每一个seed都是上一次产生的y的函数。这样，如果直接取seed＝y的话，    虽然产生的rand之间相关性甚小，但只要知道某个y，就能推知以后的rand。    为避免这种情况，一般取seed为y和当时计算机的时间的函数，如seed＝y＋t

系统里的随机数是利用初等数论中的同余定理来实现的.         比如VC中对于rand()函数是如下实现的.    int   __cdecl   rand   (void)    {    return(((holdrand =holdrand * 214013L + 2531011L) >> 16)&0x7fff);    }  

——————————————————————————————————

上面这个例子每次运行得到的结果是一样的, 这是因为对于同样的种子(seed)而言, rand产生的序列是一样的, 所以如果想每次产生的结果不一样的话，需要给srand赋予不同的种子, 比如可以取当前时间作为种子。

2. 原理

实现srand和rand并不困难， 可以采用linearcongruential generator(线性同余)的方法, 用下面的公式表示:

             Ij+1 = aIj + c (mod m)

下面的是POSIX.1-2001给出的示范实现:

[cpp] view plaincopy