伪随机数使用确定性算法根据[ 0,1 ]的均匀分布计算随机数列。 虽然不是真正的随机,但具有均匀性、独立性等随机数一样的统计特征。 计算伪随机数时,如果使用的初始值(种子)不变,伪随机数的顺序也不变。 伪随机数可以在计算机上大量生成,仿真研究中为了提高仿真效率,一般采用伪随机数代替真随机数。 仿真中,为了保证计算结果的随机性,使用循环周期极长、可以通过随机数检验的伪随机数。 [1]
中文名称
伪随机数
外语名称
仿真随机编号方法
直接法、逆转法
应用程序
程序语言
性质
名词
伪随机数生成方法
编辑
语音
一般来说,伪随机数的生成方法主要有以下三种:
(1)直接法) Direct Method )是基于分布函数的物理意义生成的。 缺点是,只能适用于具有二元分布、泊松分布等特殊分布的随机数。
(2)反演方法(Inversion Method )假设u服从[ 0,1 ]区间的均匀分布,x=f-1(u (假设u,x的累计分布函数) CDF )为f。 该方法原理简单,编程方便,适用性广。
伪随机数发生器(3)接受拒绝方法(Acceptance-Rejection Method )。 设想生成的随机数的概率密度函数(PDF )为f,首先,找到PDF为g的随机数发生器和常数c,使其成为f(xCG ) x ),并根据拒绝接收算法进行求解。 为了算法进行平均c次运算得到想生成的随机数,c的可取值必须尽可能小。 显然,该算法的缺点是很难确定g和c。
因此,伪随机数生成器[PRNG]一般采用反转法,其基础是均匀分布,均匀分布Prng的优劣决定了整个随机数体系的优劣[7]。 以下,对均匀分布的PRNG进行研究。
伪随机数程序的实例
编辑
语音
c语言程序示例
在伪随机数下,看到名为//rand01.c的c程序
#包含
staticunsignedintRAND_SEED;
是无符号随机(语音)
{
rand_seed=(rand_seed*12359 ) e536;
return(rand_seed );
}
voidRandom_start(void )。
{
inttemp[2];
move data (0x 0040,0x 006 c,FP_seg ) temp ),FP _ off (temp ),4 );
RAND_SEED=temp[0];
}
主() )
{
未指定Inti,n;
random_start (;
for(I=0; i10; I )
printf('%u(t )、random ) );
printf((n );
}
该程序(rand01.c )完整阐述了随机数产生的过程。
首先,主程序调用random_start (方法。 random_start ) )我对方法的这个语句感兴趣。
move data (0x 0040,0x 006 c,FP_seg ) temp ),FP _ off (temp ),4 );
在伪随机数理论中,该函数用于移动内存数据。 其中,FP_seg(farpointertosegment )是取得temp数组段地址的函数,FP _ off (farpointertooffset )是取得temp数组的相对地址的函数
random用于根据随机种子RAND_SEED的值计算随机数。 该文如下:
rand_seed=(rand_seed*12359 ) e536;
用于计算随机数的方法。 随机数的计算方法因计算机而异,也因安装在同一台计算机上的操作系统而异。 我们分别在linux和windows上进行了尝试,同一随机种子在这两个操作系统上生成的随机数不同,表明计算方法不同。
我们明白随机种子是从哪里得到的,我们知道随机数是怎么从随机种子计算出来的。 那么,随机种子为什么要在内存的0040:006CH上取? 0040:006CH上存储着什么?
上《计算机组成原理与接口技术》课的人可能还记得编写ROM BIOS时钟中断服务程序时使用Intel 8253计时器/计数器。 中断服务程序通过与Intel 8259中断芯片的通信运行。 主板每秒发生18.2次中断,基于处理器的计时器/计数
器值控制中断芯片产生的。在我们计算机的主机板上都会有这样一个定时/记数器用来计算当前系统时间,每过一个时钟信号周期都会使记数器加一,而这个记数器的值存放在哪儿呢?没错,就在内存的0040:006CH处,其实这一段内存空间是这样定义的:TIMER_LOW DW ? ;地址为 0040:006CH
TIMER_HIGH DW ? ;地址为 0040:006EH
TIMER_OFT DB ? ;地址为 0040:0070H
时钟中断服务程序中,每当TIMER_LOW转满时,此时,记数器也会转满,记数器的值归零,即TIMER_LOW处的16位二进制归零,而TIMER_HIGH加一。rand01.c中的
movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);
正是把TIMER_LOW和TIMER_HIGH两个16位二进制数放进temp数组,再送往RAND_SEED,从而获得了“随机种子”。
可以确定的一点是,随机种子来自系统时钟,确切地说,是来自计算机主板上的定时/计数器在内存中的记数值。这样,我们总结一下前面的分析,并讨论一下这些结论在程序中的应用:
1.随机数是由随机种子根据一定的计算方法计算出来的数值。所以,只要计算方法一定,随机种子一定,那么产生的随机数就不会变。
C++程序例
伪随机数理论推导看下面这个C++程序://rand02.cpp
#include
using namespace std;
int main()
{
unsigned int seed=5;
srand(seed);
unsigned int r=rand();
cout<
return 0;
}
在相同的平台环境下,编译生成exe后,每次运行它,显示的随机数都是一样的。这是因为在相同的编译平台环境下,由随机种子生成随机数的计算方法都是一样的,再加上随机种子一样,所以产生的随机数就是一样的。
2.只要用户或第三方不设置随机种子,那么在默认情况下随机种子来自系统时钟(即定时/计数器的值)
C++程序例2
看下面这个C++程序://rand03.cpp
#include
#include
using namespace std;
int main()
{
srand((unsigned)time(NULL));
unsigned int r=rand();
cout<
return 0;
}
这里用户和其他程序没有设定随机种子,则使用系统定时/计数器的值做为随机种子,所以,在相同的平台环境下,编译生成exe后,每次运行它,显示的随机数会是伪随机数,即每次运行显示的结果会有不同。
3.建议:如果想在一个程序中生成随机数序列,需要至多在生成随机数之前设置一次随机种子。
生成一个随机字符串
看下面这个用来生成一个随机字符串的C++程序:(原来的程序我编译不了,就改了改,加了一些头文件)(我不是上面那个括号里的人。我又对源程序进行了一下简化,可以实现相同的功能)#include
#include
#include
#define n 20
using namespace std;
int main()
{
srand (time(0));
for (int i=0;i
cout<
return 0;
}
伪随机数发生器
你可能会遇到这种情况,在VB中,在使用timer控件编制程序的时候会发现用相同的时间间隔生成的一组随机数会显得有规律,而由用户按键command事件产生的一组随机数却显得比较随机,为什么?根据我们上面的分析,你可以很快想出答案。这是因为timer是由计算机时钟记数器精确控制时间间隔的控件,时间间隔相同,记数器前后的值之差相同,这样时钟取值就是呈线性规律的,所以随机种子是呈线性规律的,生成的随机数也是有规律的。而用户按键事件产生随机数确实更呈现随机性,因为事件是由人按键引起的,而人不能保证严格的按键时间间隔,即使严格地去做,也不可能完全精确做到,只要时间间隔相差一微秒,记数器前后的值之差就不相同了,随机种子的变化就失去了线性规律,那么生成的随机数就更没有规律了,所以这样生成的一组随机数更随机。这让我想到了各种晚会的抽奖程序,如果用人来按键产生幸运观众的话,那就会很好的实现随机性原则,结果就会更公正。
总结
1.计算机的伪随机数是由随机种子根据一定的计算方法计算出来的数值。所以,只要计算方法一定,随机种子一定,那么产生的随机数就是固定的。
2.只要用户或第三方不设置随机种子,那么在默认情况下随机种子来自系统时钟。
伪随机数生成器缺点
编辑
语音
重复做N=10000次试验,每次产生S=20与S=100个随机分布的样本,同时采用Kolmogorov- Smirnov假设检验(hypothesis test)来确定样本是否满足均匀分布。规定:
① 0假设(null hypothesis)为样本服从均匀分布;② 1假设(alternative hypothesis)为样本不服从均匀分布。
采用P值(∈[0, 1])衡量,P值越趋近于0,表示越有理由拒绝0假设,即样本不服从均匀分布;P值越趋近于1,表示越有理由接受0假设,即样本服从均匀分布。
随着P值下降,样本也越来越不服从均匀分布。实践中希望P值越大越好。然而统计学的结论显示,P值一定服从均匀分布,与N、S大小无关,这表明由于随机性,总会出现某次抽样得到的样本不服从、甚至远离均匀分布。另外,样本大小的不同,造成检验标准的不同,直观上看S=100对应的均匀分布普遍比S=20对应的更均匀。因此,小样本情况下均匀分布PRNG的差异性尤为严重。
词条图册
更多图册
参考资料
1.
陆雄文.管理学大辞典:上海辞书出版社,2013年