正文

计算机产生的随机数[1]2008-05-03 01:23:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/34769.html

分享到:

写在最前面。我有一个朋友,一个女程序员,她的业余爱好是写小说,我看着她的小说里栩栩如生的人物觉得很了不起,她的脑子里可以想这么多好玩的人和事,于是我问,你为什么写小说啊,她只是简单的回答,我只是想写点很好的东西。我写不来那些,但我也希望我写的东西很好,我尽全力。

这篇由几个帖子引出,也是一直争论的焦点,std::rand()的性能怎样,随机数如何才算‘随机’,随机数如何检验。

它们是:

http://www.programfan.com/club/post-273908.html
http://www.programfan.com/club/post-274446.html

1 随机数的应用

随机数应用在哪些方面?std::rand()有什么用?统计学在生产活动中有着非常广泛的应用,它深刻地影响到了科学界和人们的生活。工厂的产品检验,人口的普查,国家还有专门的统计局,资源能源等,几乎都离不开统计学。科学界,决策论,贝叶斯决策已经形成独立的理论,随机过程,计算机模拟,计算机访真,还有密码学,都是随着现代概率论和统计学的成熟而发展起来的一大批科学。

就计算机中的随机数来说,主要用处有2个:1,用于抽样的编号。这也是最原始和最主要的用途了,在没有计算机之前,人们是用随机数表来进行抽样的,做一个足够大的表,表中的数据是通过物理过程模拟得到,比如丢色子。比如,医学上有一种随机数表,叫乱数表,它是一个n*n的矩阵,每一个格子中填一个数字0-9,数字是混乱的,医学实验时,是这样得到随机数序列的,手指随便一指,指到一个格子,然后随机选一个方向,比如向右,然后延着这个方向读几个数字,组成随机数,然后将它平移到需要的范围内,比如,你要[0,150]的随机数,你得到的数字是378,那进行平移,378-150-150=78,就是78这个数。2,用于计算机模拟。比如统计计算中形成的一大类计算方法,蒙特卡罗方法,就是一种随机计算方法。比如,模拟退火算法中,会按当前温度和邻解和当前解的目标值差计算出一个概率值p,然后依这个概率p接受或者拒绝这个邻解,如果p=0.5,那就有一半的机会接受。再比如,遗传算法中的交叉概率和变异概率,都需要用到随机数来进行模拟。

2 随机数的经典产生

std::rand()算是比较经典的产生了。计算机产生之后,一开始只是将随机数表搬计算机的存储器,而本质上和原来没有改变,之后才形成了更好的方法,通过一些方法可以得到一个伪随机序列,它是一个周期序列,像x1,x2,...xn,x1,x2,...,它的周期是T,同时再给出一些种子值s1,s2,...sn,s1,s2,...如果当前种子值是si那产生的随机值一定是xi,这个序列是确定的,就像一个很大的随机数表,我们只要随机给个种子值,就可以从中得到一小段很好的随机子序列,而这个种子我们常用当前系统时间来得到。因为你让程序跑起来的时间是变化的,所以给人的假相就是,它像真的随机了!

以下是一种实现:

/***
*rand.c - random number generator
*
*       Copyright (c) 1985-1997, Microsoft Corporation. All rights reserved.
*
*Purpose:
*       defines rand(), srand() - random number generator
*
*******************************************************************************/

#include <cruntime.h>
#include <mtdll.h>
#include <stddef.h>
#include <stdlib.h>

#ifndef _MT
static long holdrand = 1L;
#endif  /* _MT */

/***
*void srand(seed) - seed the random number generator
*
*Purpose:
*       Seeds the random number generator with the int given.  Adapted from the
*       BASIC random number generator.
*
*Entry:
*       unsigned seed - seed to seed rand # generator with
*
*Exit:
*       None.
*
*Exceptions:
*
*******************************************************************************/

void __cdecl srand (
        unsigned int seed
        )
{
#ifdef _MT

        _getptd()->_holdrand = (unsigned long)seed;

#else  /* _MT */
        holdrand = (long)seed;
#endif  /* _MT */
}


/***
*int rand() - returns a random number
*
*Purpose:
*       returns a pseudo-random number 0 through 32767.
*
*Entry:
*       None.
*
*Exit:
*       Returns a pseudo-random number 0 through 32767.
*
*Exceptions:
*
*******************************************************************************/

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 */
}

[VC6中的版本]

种子值的递推式是:

seed = seed *214013L+2531011L

返回值和种子值的关系是:

return = (seed>>16) & 0x7fff

即取seed的高16位。随机数的其它产生方法可以查阅统计计算方面的书籍,而接下来讨论的重点是,如何检验随机数。

[未完待续]

阅读(8088) | 评论(2)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册