学步园

1. 示例:

下面是一个C语言中使用随机函数的例子:  

#include <stdlib.h><br /> #include <stdio.h><br /> int main()<br /> {<br /> srand(1);<br /> for(int i = 0; i < 10; i++)<br /> {<br /> printf("%d : %d/n", i, rand());<br /> }<br /> }<br />

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

2. 原理

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

              Ij+1 = aIj + c (mod m)

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

static unsigned long next = 1;</p> <p>/* RAND_MAX assumed to be 32767 */<br /> int myrand(void) {<br /> next = next * 1103515245 + 12345;<br /> return((unsigned)(next/65536) % 32768);<br /> }</p> <p>void mysrand(unsigned seed) {<br /> next = seed;<br /> }<br />

3. VC9和GLIBC2.3的实现

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

#define RAND_MAX 0x7fff</p> <p>void __cdecl srand (<br /> unsigned int seed<br /> )<br /> {</p> <p> _getptd()->_holdrand = (unsigned long)seed;</p> <p>}</p> <p>int __cdecl rand (<br /> void<br /> )<br /> {</p> <p> _ptiddata ptd = _getptd();</p> <p> return( ((ptd->_holdrand = ptd->_holdrand * 214013L<br /> + 2531011L) >> 16) & 0x7fff );</p> <p>}

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

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

<br /> weak_alias (__srandom, srand)</p> <p>void<br /> __srandom (x)<br /> unsigned int x;<br /> {<br /> __libc_lock_lock (lock);<br /> (void) __srandom_r (x, &unsafe_state);<br /> __libc_lock_unlock (lock);<br /> }</p> <p>int<br /> __srandom_r (seed, buf)<br /> unsigned int seed;<br /> struct random_data *buf;<br /> {<br /> int type;<br /> int32_t *state;<br /> long int i;<br /> long int word;<br /> int32_t *dst;<br /> int kc;</p> <p> if (buf == NULL)<br /> goto fail;<br /> type = buf->rand_type;<br /> if ((unsigned int) type >= MAX_TYPES)<br /> goto fail;</p> <p> state = buf->state;<br /> /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */<br /> if (seed == 0)<br /> seed = 1;<br /> state[0] = seed;<br /> if (type == TYPE_0)<br /> goto done;</p> <p> dst = state;<br /> word = seed;<br /> kc = buf->rand_deg;<br /> for (i = 1; i < kc; ++i)<br /> {<br /> /* This does:<br /> state[i] = (16807 * state[i - 1]) % 2147483647;<br /> but avoids overflowing 31 bits. */<br /> long int hi = word / 127773;<br /> long int lo = word % 127773;<br /> word = 16807 * lo - 2836 * hi;<br /> if (word < 0)<br /> word += 2147483647;<br /> *++dst = word;<br /> }</p> <p> buf->fptr = &state[buf->rand_sep];<br /> buf->rptr = &state[0];<br /> kc *= 10;<br /> while (--kc >= 0)<br /> {<br /> int32_t discard;<br /> (void) __random_r (buf, &discard);<br /> }</p> <p> done:<br /> return 0;</p> <p> fail:<br /> return -1;<br /> }</p> <p>int<br /> rand ()<br /> {<br /> return (int) __random ();<br /> }</p> <p>long int<br /> __random ()<br /> {<br /> int32_t retval;</p> <p> __libc_lock_lock (lock);</p> <p> (void) __random_r (&unsafe_state, &retval);</p> <p> __libc_lock_unlock (lock);</p> <p> return retval;<br /> }</p> <p>int<br /> __random_r (buf, result)<br /> struct random_data *buf;<br /> int32_t *result;<br /> {<br /> int32_t *state;</p> <p> if (buf == NULL || result == NULL)<br /> goto fail;</p> <p> state = buf->state;</p> <p> if (buf->rand_type == TYPE_0)<br /> {<br /> int32_t val = state[0];<br /> val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;<br /> state[0] = val;<br /> *result = val;<br /> }<br /> else<br /> {<br /> int32_t *fptr = buf->fptr;<br /> int32_t *rptr = buf->rptr;<br /> int32_t *end_ptr = buf->end_ptr;<br /> int32_t val;</p> <p> val = *fptr += *rptr;<br /> /* Chucking least random bit. */<br /> *result = (val >> 1) & 0x7fffffff;<br /> ++fptr;<br /> if (fptr >= end_ptr)<br /> {<br /> fptr = state;<br /> ++rptr;<br /> }<br /> else<br /> {<br /> ++rptr;<br /> if (rptr >= end_ptr)<br /> rptr = state;<br /> }<br /> buf->fptr = fptr;<br /> buf->rptr = rptr;<br /> }<br /> return 0;</p> <p> fail:<br /> __set_errno (EINVAL);<br /> return -1;<br /> }</p> <p>

在有些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实现:

int<br /> rand_r (unsigned int *seed)<br /> {<br /> unsigned int next = *seed;<br /> int result;</p> <p> next *= 1103515245;<br /> next += 12345;<br /> result = (unsigned int) (next / 65536) % 2048;</p> <p> next *= 1103515245;<br /> next += 12345;<br /> result <<= 10;<br /> result ^= (unsigned int) (next / 65536) % 1024;</p> <p> next *= 1103515245;<br /> next += 12345;<br /> result <<= 10;<br /> result ^= (unsigned int) (next / 65536) % 1024;</p> <p> *seed = next;</p> <p> return result;<br /> }

5. 其他考虑

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

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

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

6. 推荐书籍

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