论文部分内容阅读
[摘要]本文对随机数均匀分布、正态分布的生成算法进行了探讨,给出了一种服从正态分布随机数生成方法,该方法用于描述取值范围较集中的现象,它在客观世界中有着广泛的应用。
[关键词]随机数均匀分布正态分布教学
一、引言
在数据结构、算法分析与设计、科学模拟、信息安全等方面都需要用到随机数。特别是一些安全级别要求比较高的应用,对于随机数的质量提出了很高的要求。随机数的生成一般有两种方式,一种是硬件方式,一种是软件方式。一般情况下,硬件方式生成的随机数质量要好于软件方式生成的随机数。但是对于一般的用户来说,需要每位用户都配备一种硬件设备来生成随机数,这种方式可能不太现实。因此,通过软件方式来寻找高质量的随机数,这是一个很重要而且人们不断探讨的课题。
最早遇到的随机数是大学一年级学习C语言中的rand()函数。rand()返回一个0~32767的整数。像rand()这样的随机数生成函数是以等概率的形式产生的均匀分布,对于描述等概率事件的现实问题是一个不错的随机数发生器;而现实世界大多事件服从正态分布,像打靶射击模拟、统计分析等很多事件都服从正太分布。那么如何设计服从正态分布的随机数生成器呢?这对学生来说这是一个新的、挑战性课题。
二、基础知识
随着概率统计的学习,学生逐渐认识、理解正态分布、大数定律和中心极限定理。这些理论描述了从大量随机现象中寻找必然的法则。
(1)正态分布
密度函数为: 。
分布曲线如图1所示。正态分布是概率论中最重要的一种分布,它在客观世界中有着广泛的应用。通常随机变量的取值范围较集中的现象。
生产与科学实验中很多随机变量的概率分布都可以近似地用正态分布来描述。例如,在生产条件不变的情况下,产品的强力、抗压强度、口径、长度等指标;同一种生物体的身长、体重等指标;同一种种子的重量;测量同一物体的误差;弹着点沿某一方向的偏差;某个地区的年降水量;以及理想气体分子的速度分量,等等。
(2)大数定律
大数定律科学地描述了大量的随机现象中平均值的稳定性。
(3)中心极限定理
设随机变量 相互独立,服从同一分布且有有限的数学期望μ和方差σ2,则随机变量 ,在n无限增大时,服从参数为μ和的正态分布即n→∞时, 。
中心极限定理表明,大量的独立随机变量之和具有近似于正态的分布。因此,它不仅提供了计算独立随机变量之和的近似概率的简单方法,而且有助于解释为什么有很多自然群体的经验频率呈现出钟形(即正态)曲线这一事实,因此中心极限定理这个结论使正态分布在数理统计中具有很重要的地位,也使正态分布有了广泛的应用。
3.算法设计与实现
如果我们以服从同一分布的独立随机变量的和作为随机数,根据中心极限定理,该随机数服从正态分布。依此,我们选取服从均匀分布的随机变量的和来产生服从正态分布的随机数,服从均匀分布的随机变量可由rand()产生。
(1)取均匀分布为随机变量,{xi}是在[a,b]上服从均匀分布的随机变量序列,期望为:E{xi}=(a+b)/2,方差为:D{xi}=(b-a)2/12,
(2)由中心极限定理,n个均匀随机数的和Σxi,将逼近正态分布N(n(a+b)/2,n(b-a)2/12) 。
特别地,若取[-1,1]上的均匀分布,n取3,即三个均匀随机数的和,则Σxi逼近标准正态分布N(0,1)。
算法描述:
1)产生三个32位的且在[-1,1]上(带符号)随机数;
①由rand()产生一个整数;
②将整数进行异或移位运算,目的是产生带符号随机数;
③经过求商,再将它转化为[-1.0,1.0] 上(带符号)随机数。
2)将三个32位的带符号随机数相加,就得到一个服从正态分布的随机数。
具体代码描述如下:
(3)作为比较,我们分别利用rand()和N_rand()进行了二维和三维可视化描述实验,结果如下图2、图3所示,效果很好。实验中随机数的范围都取在[-1.0,1.0]。
四、结论
上述生成服从正态分布随机数方法简单高效,该方法用于描述取值范围较集中的现象,它在客观世界中有着广泛的应用。
在教学中,教师从基础知识入手,结合学生学习功课的入深,把实际应用问题恰当得插入教学当中,由浅入深,综合运用程序设计、高等数学、数据结构、计算机图形等各门课程知识,激发学生学习和探求的热情;能够起到育物细无声的作用,对培养学生的分析问题和解决问题的能力和创新意识具有重要的意义。
[参考文献]
[1] 谭阳,全惠云, 一种生成动态随机数的并行算法, 计算机工程, 2009,35(13),150-152
[2] 戴毅,周江华 等,正态随机变量生成的直方图抽样算法,系统仿真学报,2007,19(17),3888-3890
[3] (美)H.M.Deitel, P.J.Deitel, 薛万鹏 等译, C程序设计教程, 北京:机械工业出版社,2007.12
[4] (美)项志钢, 计算机图形学,清华大学出版社,2008.7
(作者单位:常州大学信息科学与工程学院)
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
[关键词]随机数均匀分布正态分布教学
一、引言
在数据结构、算法分析与设计、科学模拟、信息安全等方面都需要用到随机数。特别是一些安全级别要求比较高的应用,对于随机数的质量提出了很高的要求。随机数的生成一般有两种方式,一种是硬件方式,一种是软件方式。一般情况下,硬件方式生成的随机数质量要好于软件方式生成的随机数。但是对于一般的用户来说,需要每位用户都配备一种硬件设备来生成随机数,这种方式可能不太现实。因此,通过软件方式来寻找高质量的随机数,这是一个很重要而且人们不断探讨的课题。
最早遇到的随机数是大学一年级学习C语言中的rand()函数。rand()返回一个0~32767的整数。像rand()这样的随机数生成函数是以等概率的形式产生的均匀分布,对于描述等概率事件的现实问题是一个不错的随机数发生器;而现实世界大多事件服从正态分布,像打靶射击模拟、统计分析等很多事件都服从正太分布。那么如何设计服从正态分布的随机数生成器呢?这对学生来说这是一个新的、挑战性课题。
二、基础知识
随着概率统计的学习,学生逐渐认识、理解正态分布、大数定律和中心极限定理。这些理论描述了从大量随机现象中寻找必然的法则。
(1)正态分布
密度函数为: 。
分布曲线如图1所示。正态分布是概率论中最重要的一种分布,它在客观世界中有着广泛的应用。通常随机变量的取值范围较集中的现象。
生产与科学实验中很多随机变量的概率分布都可以近似地用正态分布来描述。例如,在生产条件不变的情况下,产品的强力、抗压强度、口径、长度等指标;同一种生物体的身长、体重等指标;同一种种子的重量;测量同一物体的误差;弹着点沿某一方向的偏差;某个地区的年降水量;以及理想气体分子的速度分量,等等。
(2)大数定律
大数定律科学地描述了大量的随机现象中平均值的稳定性。
(3)中心极限定理
设随机变量 相互独立,服从同一分布且有有限的数学期望μ和方差σ2,则随机变量 ,在n无限增大时,服从参数为μ和的正态分布即n→∞时, 。
中心极限定理表明,大量的独立随机变量之和具有近似于正态的分布。因此,它不仅提供了计算独立随机变量之和的近似概率的简单方法,而且有助于解释为什么有很多自然群体的经验频率呈现出钟形(即正态)曲线这一事实,因此中心极限定理这个结论使正态分布在数理统计中具有很重要的地位,也使正态分布有了广泛的应用。
3.算法设计与实现
如果我们以服从同一分布的独立随机变量的和作为随机数,根据中心极限定理,该随机数服从正态分布。依此,我们选取服从均匀分布的随机变量的和来产生服从正态分布的随机数,服从均匀分布的随机变量可由rand()产生。
(1)取均匀分布为随机变量,{xi}是在[a,b]上服从均匀分布的随机变量序列,期望为:E{xi}=(a+b)/2,方差为:D{xi}=(b-a)2/12,
(2)由中心极限定理,n个均匀随机数的和Σxi,将逼近正态分布N(n(a+b)/2,n(b-a)2/12) 。
特别地,若取[-1,1]上的均匀分布,n取3,即三个均匀随机数的和,则Σxi逼近标准正态分布N(0,1)。
算法描述:
1)产生三个32位的且在[-1,1]上(带符号)随机数;
①由rand()产生一个整数;
②将整数进行异或移位运算,目的是产生带符号随机数;
③经过求商,再将它转化为[-1.0,1.0] 上(带符号)随机数。
2)将三个32位的带符号随机数相加,就得到一个服从正态分布的随机数。
具体代码描述如下:
(3)作为比较,我们分别利用rand()和N_rand()进行了二维和三维可视化描述实验,结果如下图2、图3所示,效果很好。实验中随机数的范围都取在[-1.0,1.0]。
四、结论
上述生成服从正态分布随机数方法简单高效,该方法用于描述取值范围较集中的现象,它在客观世界中有着广泛的应用。
在教学中,教师从基础知识入手,结合学生学习功课的入深,把实际应用问题恰当得插入教学当中,由浅入深,综合运用程序设计、高等数学、数据结构、计算机图形等各门课程知识,激发学生学习和探求的热情;能够起到育物细无声的作用,对培养学生的分析问题和解决问题的能力和创新意识具有重要的意义。
[参考文献]
[1] 谭阳,全惠云, 一种生成动态随机数的并行算法, 计算机工程, 2009,35(13),150-152
[2] 戴毅,周江华 等,正态随机变量生成的直方图抽样算法,系统仿真学报,2007,19(17),3888-3890
[3] (美)H.M.Deitel, P.J.Deitel, 薛万鹏 等译, C程序设计教程, 北京:机械工业出版社,2007.12
[4] (美)项志钢, 计算机图形学,清华大学出版社,2008.7
(作者单位:常州大学信息科学与工程学院)
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文