《随机函数random(n)的实现》

随机函数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);   
}  

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

1. #include <stdlib.h> 
2. #include <stdio.h> 
3. int main() 
4. { 
5.     srand(1); 
6.     for(int i = 0; i < 10; i++) 
7.     { 
8.          printf("%d : %d/n", i, rand()); 
9.     } 
10. } 

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

2. 原理

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

             Ij+1 = aIj + c (mod m)

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

[cpp] view plaincopy

1. static unsigned long next = 1; 
2.   
3. /* RAND_MAX assumed to be 32767 */ 
4. int myrand(void) { 
5.     next = next * 1103515245 + 12345; 
6.     return((unsigned)(next/65536) % 32768); 
7. } 
8.   
9. void mysrand(unsigned seed) { 
10.     next = seed; 
11. }