学步园

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

3.VC9和GLIBC2.3的实现

 VC9里面CRT代码中可以查到rand和srand的实现, 摘录录下:

[cpp] view plaincopy

12. #define RAND_MAX 0x7fff 
13.   
14. void __cdecl srand (  unsigned int seed  ) 
15. { 
16.   
17.         _getptd()->_holdrand = (unsigned long)seed; 
18.   
19. } 
20.   
21. int __cdecl rand (  void  ) 
22. { 
23.   
24.         _ptiddata ptd = _getptd(); 
25.   
26.         return( ((ptd->_holdrand = ptd->_holdrand * 214013L 
27.             + 2531011L) >> 16) & 0x7fff ); 
28.   
29. } 

可以看出VC里面rand函数返回的最大值是0x7fff，即32767, 由上面的代码可以理解为什么给定同样的seed, 得出的序列是一样的。

Glibc2.3里面关于rand和srand的实现要复杂很多, 采用的non-linearadditive
feedback random number generator, rand返回的最大值是2147483647 (2**31 -1), 下面是参考代码:

[cpp] view plaincopy

30. weak_alias (__srandom, srand) 
31.   
32. void 
33. __srandom (x) 
34.      unsigned int x; 
35. { 
36.   __libc_lock_lock (lock); 
37.   (void) __srandom_r (x, &unsafe_state); 
38.   __libc_lock_unlock (lock); 
39. } 
40.   
41. int 
42. __srandom_r (seed, buf) 
43.      unsigned int seed; 
44.      struct random_data *buf; 
45. { 
46.   int type; 
47.   int32_t *state; 
48.   long int i; 
49.   long int word; 
50.   int32_t *dst; 
51.   int kc; 
52.   
53.   if (buf == NULL) 
54.     goto fail; 
55.   type = buf->rand_type; 
56.   if ((unsigned int) type >= MAX_TYPES) 
57.     goto fail; 
58.   
59.   state = buf->state; 
60.   /* We must make sure the seed is not 0.  Take arbitrarily 1 in this case.  */ 
61.   if (seed == 0) 
62.     seed = 1; 
63.   state[0] = seed; 
64.   if (type == TYPE_0) 
65.     goto done; 
66.   
67.   dst = state; 
68.   word = seed; 
69.   kc = buf->rand_deg; 
70.   for (i = 1; i < kc; ++i) 
71.     { 
72.       /* This does:
73.        state[i] = (16807 * state[i - 1]) % 2147483647;
74.      but avoids overflowing 31 bits.  */ 
75.       long int hi
    = word / 127773; 
76.       long int lo = word % 127773; 
77.       word = 16807 * lo - 2836 * hi; 
78.       if (word < 0) 
79.     word += 2147483647; 
80.       *++dst = word; 
81.     } 
82.   
83.   buf->fptr = &state[buf->rand_sep]; 
84.   buf->rptr = &state[0]; 
85.   kc *= 10; 
86.   while (--kc >= 0) 
87.     { 
88.       int32_t discard; 
89.       (void) __random_r (buf, &discard); 
90.     } 
91.   
92.  done: 
93.   return 0; 
94.   
95.  fail: 
96.   return -1; 
97. } 
98.   
99.   
100. int 
101. rand () 
102. { 
103.   return (int)
     __random (); 
104. } 
105.   
106. long int 
107. __random () 
108. { 
109.   int32_t retval; 
110.   
111.   __libc_lock_lock (lock); 
112.   
113.   (void) __random_r (&unsafe_state, &retval); 
114.   
115.   __libc_lock_unlock (lock); 
116.   
117.   return retval; 
118. } 
119.   
120. int 
121. __random_r (buf, result) 
122.      struct random_data *buf; 
123.      int32_t *result; 
124. { 
125.   int32_t *state; 
126.   
127.   if (buf == NULL || result == NULL) 
128.     goto fail; 
129.   
130.   state = buf->state; 
131.   
132.   if (buf->rand_type == TYPE_0) 
133.     { 
134.       int32_t val = state[0]; 
135.       val = ((state[0] * 1103515245) + 12345) & 0x7fffffff; 
136.       state[0] = val; 
137.       *result = val; 
138.     } 
139.   else 
140.     { 
141.       int32_t *fptr = buf->fptr; 
142.       int32_t *rptr = buf->rptr; 
143.       int32_t *end_ptr = buf->end_ptr; 
144.       int32_t val; 
145.   
146.       val = *fptr += *rptr; 
147.       /* Chucking least random bit.  */ 
148.       *result = (val >> 1) & 0x7fffffff; 
149.       ++fptr; 
150.       if (fptr >= end_ptr) 
151.     { 
152.       fptr = state; 
153.       ++rptr; 
154.     } 
155.       else 
156.     { 
157.       ++rptr; 
158.       if (rptr >= end_ptr) 
159.         rptr = state; 
160.     } 
161.       buf->fptr = fptr; 
162.       buf->rptr = rptr; 
163.     } 
164.   return 0; 
165.   
166.  fail: 
167.   __set_errno (EINVAL); 
168.   return -1; 
169. } 

在有些rand函数的实现里面，高位比低位的随机性更强, 所以如果要产生1-10之间的随机数，最好用:

j = 1 + (int) (10.0 *(rand() / (RAND_MAX + 1.0)));

而不要用:

 j = 1 + (rand() %10);

4. 多线程安全版本

rand不是多线程安全也不是可重入的，在多线程环境下，给定同样的种子，跑出来的序列可能是不一样的，因为实现里面用到了静态变量，在多线程环境下应该使用rand_r函数 (windows上使用rand_s), 下面是glibc的rand_r实现:

[cpp] view plaincopy

170. int 
171. rand_r (unsigned int *seed) 
172. { 
173.   unsigned int next = *seed; 
174.   int result; 
175.   
176.   next *= 1103515245; 
177.   next += 12345; 
178.   result = (unsigned int) (next / 65536) % 2048; 
179.   
180.   next *= 1103515245; 
181.   next += 12345; 
182.   result <<= 10; 
183.   result ^= (unsigned int) (next / 65536) % 1024; 
184.   
185.   next *= 1103515245; 
186.   next += 12345; 
187.   result <<= 10; 
188.   result ^= (unsigned int) (next / 65536) % 1024; 
189.   
190.   *seed = next; 
191.   
192.   return result; 
193. } 

5. 其他考虑

游戏里面大量的应用到了随机函数，比如彩票，炼器功能，有意思的是玩家对这些随机时间会比较迷信，经常有各种搞笑的说话，比如在某个NPC下面炼器成功概率高啊, 炼器的时候骂人会提高成功率...

这里有个问题，玩家炼器经常采用垫装备的方法，这个方法简单而言就是先拿几个烂的装备等连续炼失败了几次以后再去上一个好装备，这样会不会提高最后那个好装备的成功概率呢？

个人觉得这个和实现相关，假如每次成功的概率都是50%, 如果前面N次序列都是小于50%，那么第N+1次概率是有可能受影响的，也即随机序列里面的元素并不是完全独立，序列之间是有关系，个人觉得通过这种方面在某种程度能提高成功的概率，但是还要考虑到会受游戏中别的玩家的干扰以及实现的时候可能每次使用不同的种子等的影响。

6. 推荐书籍

Numerical Recipes in C:The Art of Scientific Computing Second Edition: 第七章