随机数生成原理 实现方法 不同编程语言的随机数函数

1-0：MicrosoftVC++产生随机数的原理：Srand()和Rand()函数。它本质上是利用线性同余法，y=ax+b(modm)。其中a，b，m都是常数。因此rand的产生决定于x，x被称为Seed。Seed需要程序中设定，一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小，取值范围是0—32767（int），即双字节（16位数），若用unsignedint双字节是65535，四字节是4294967295，一般可以满足要求。1-1：线性同余法：其中M是模数，A是乘数，C是增量，为初始值，当C=0时，称此算法为乘同余法；若C≠0，则称算法为混合同余法，当C取不为零的适当数值时，有一些优点，但优点并不突出，故常取C=0。模M大小是发生器周期长短的主要标志，常见有M为素数，取A为M的原根，则周期T=M-1。例如：a=1220703125a=32719（程序中用此组数）a=16807代码：voidmain(){constintn=100;doublea=32719,m=1,f[n+1],g[n],seed;m=pow(2,31);cout设置m值为m-1endl;cout输入种子endl;//输入种子cinseed;f[0]=seed;for(inti=1;i=n;i++)//线性同余法生成随机数{f[i]=fmod((a*f[i-1]),(m-1));g[i-1]=f[i]/(m-1);cout.setf(ios::fixed);cout.precision(6);//设置输出精度couti'\t'g[i-1]endl;}}结果分析：统计数据的平均值为：0.485653统计数据的方差为：0.3205761-2：人字映射递推公式就是有名的混沌映射中的“人字映射”或称“帐篷映射”，它的非周期轨道点的分布密度函数：人字映射与线性同余法结合，可产生统计性质优良的均匀随机数。for(inti=1;i=n;i++)//线性同余法生成随机数{f[i]=fmod((a*f[i-1]),m);if(f[i]=m/2)//与人字映射结合生成随机数{f[i]=2*f[i];}else{f[i]=2*(m-f[i])+1;}1-3：平方取中法——冯•诺伊曼1946年前后，由冯•诺伊曼提出，他的办法是去前面的随机数的平方，并抽取中部的数字。例如要生成10位数字，而且先前的值是5772156649，平方后得到33317792380594909201，所以下一个数是7923805949。for(j=1;j=n;j++){i[j]=i[j-1]*i[j-1];i[j]=i[j]/pow(10,5);i[j]=fmod(i[j],pow(10,10));g[j]=i[j]/pow(10,10);cout.setf(ios::fixed);cout.precision(6);//设置输出精度coutj'\t'g[j]endl;}二：任意分布随机数的生成利用(0，1)均匀分布的随机数可以产生任意分布的随机数。主要的方法有反函数法，舍选法，离散逼近法，极限近似法和随机变量函数法等。这里主要讨论了反函数法，当然对于具体分布函数可以采用不同的方法。设随机变量X具有分布函数F(X)，则对一个给定的分布函数值，X的值为其中inv表示反函数。现假设r是(0，1)均匀分布的随机变量R的一个值，已知R的分布函数为因此，如果r是R的一个值，则X具有概率也就是说如果(r1,r2,...,rn)是R的一组值，则相应可得到的一组值具有分布。从而，如果我们已知分布函数的反函数，我们就可以从(0，1)分布的均匀分布随机数得到所需分布的随机数了。1-4：指数分布：指数分布的分布函数为:x0时,F(x)=0；,F(x)=1-exp利用上面所述反函数法，可以求得:x=ln(1-y)，这里不妨取常数为1.for(intj=0;jn;j++){i=rand()%100;//产生从0-32767的任意一个值a[j]=double(i)/double(100);a[j]=-log(a[j]);//常数大于0，这里取1、、、、、、、1-5：正态分布：正态分布的概率密度是：正态分布的分布函数是：对于正态分布，利用反函数的方法来获取正态分布序列显然是很麻烦的，牵涉到很复杂的积分微分运算，同时为了方便，我们取，即标准正态分布。因此这里介绍了两种算法：第一种：Box和Muller在1958年给出了由均匀分布的随机变量生成正态分布的随机变量的算法。设U1,U2是区间(0,1)上均匀分布的随机变量，且相互独立。令X1=sqrt(-2*log(U1))*cos(2*PI*U2);X2=sqrt(-2*log(U1))*sin(2*PI*U2);那么X1,X2服从N(0,1)分布，且相互独立。p=rand()%100;//产生从0-32767的任意一个值b[j]=double(p)/double(100);a[j]=sqrt(-2*log(a[j]))*cos(2*3.1415926*b[j]);第二种：近似生成标准正态分布，独立同分布的多个随机变量和的分布趋近于正态分布,取k个均匀分布的(0,1)随机变量，，……，则它们的和近似服从正态分布。实践中,取k=12,(因为D()=1/12),则新的随机变量y=x1+x2+...+x12-6，可以求出数学期望E(y)=0,方差D(y)=12*1/12=1，因此可以近似描述标准正态分布这几天再看数据结构和算法，中间遇到了生成不重复的随机数的问题我先想到的一个算法是这样的：Generator(vectorint&vec,constintnum){srand(time(NULL));vectorintv;intsize=num;for(inti=1;i=num;++i){v.push_back(i);}for(inti=0;inum;++i){vectorint::iteratorit=v.begin();intn=rand()%(size--);it+=n;vec.push_back(*it);v.erase(it);}}但是由于vector删除效率很低，所以这个算法在10W的时候已经不可接受了，需要17秒左右，后来在网上看到有朋友提出了另一种算法，感觉不错，于是又测试了一下voidGen(vectorint&vec,constintnum){srand(time(NULL));for(inti=0;inum;++i)vec.push_back(i+1);for(inti=0;inum;++i)swap(vec.at(i),vec.at(rand()%num));}这个算法是线性的，在10W的时候还可以，需要1.7秒左右，可是100W的时候就要17秒左右了。想问一下，有没有更高效的生成算法？________________________________________回复：问一个关于随机数生成算法的问题lz应该把要求说的具体点一定要vector?________________________________________回复：问一个关于随机数生成算法的问题同意楼上的。要生成不重复的随机数，楼主可以自己写一个随机数生成程序啊，为什么一定要用rand()函数？楼主如果真的对随机数感兴趣，建议楼主看一看Knuth的《计算机程序设计艺术》第二卷。可以用线性同余法:A(n+1)=(a*A(n)+c)%M生成取遍1至M-1的所有整数，前提是参数a,c,M选取合适。________________________________________回复：问一个关于随机数生成算法的问题STL主要目标是提供一个通用高速的算法，如果对一个专用的功能而且追求很高的效率，最好使用最原始数据类型和直接手写的算法。下面给出我刚刚写好的一个程序，在VC6下编译通过，当n=100万时，仅需0.78秒。//csdn_5398401.cpp:Definestheentrypointfortheconsoleapplication.#includestdafx.h#includememory.h#includestdlib.h#includewindows.htypedefunsignedcharBYTE;typedefunsignedlongDWORD;voidtest(intn){inti,c;DWORDidx;DWORD*pBuff;BYTE*pMask;BYTEmaskArr[]={1,2,4,8,16,32,64,128};//----------c=(n+7)/8;pMask=newBYTE[c];pBuff=newDWORD[n];memset(pMask,0,sizeof(BYTE)*c);memset(pBuff,0,sizeof(DWORD)*n);for(i=1;in;){idx=(rand()15)+rand();idx%=n;//随机得到一个0ton之间地址，nx=0,if((pMask[idx/8]&maskArr[idx%8])==0)//pBuff[x]没有存储过任何数{pMask[idx/8]|=maskArr[idx%8];//置1pBuff[idx]=i;i++;}}//---------delete[]pMask;delete[]pBuff;}intmain(intargc,char*argv[]){DWORDt=GetTickCount();test(1000000);t=GetTickCount()-t;printf(Ittake%dms\n,t);return0;}Java中随机数生成的几种方法java产生随机数的几种方式在j2se里我们可以使用Math.random()方法来产生一个随机数，这个产生的随机数是0-1之间的一个double，我们可以把他乘以一定的数，比如说乘以100，他就是个100以内的随机，这个在j2me中没有。在java.util这个包里面提供了一个Random的类，我们可以新建一个Random的对象来产生随机数，他可以产生随机整数、随机float、随机double，随机long，这个也是我们在j2me的程序里经常用的一个取随机数的方法。在我们的System类中有一个currentTimeMillis()方法，这个方法返回一个从1970年1月1号0点0分0秒到目前的一个毫秒数，返回类型是long，我们可以拿他作为一个随机数，我们可以拿他对一些数取模，就可以把他限制在一个范围之内啦其实在Random的默认构造方法里也是使用上面第三种方法进行随机数的产生的对于方法二中的Random类有以下说明：java.util.Random类有两种方式构建方式：带种子和不带种子不带种子：此种方式将会返回随机的数字，每次运行结果不一样publicclassRandomTest{publicstaticvoidmain(String[]args){java.util.Randomr=newjava.util.Random();for(inti=0;i10;i++){System.out.println(r.nextInt());}}带种子：此种方式，无论程序运行多少次，返回结果都是一样的publicstaticvoidmain(String[]args){java.util.Randomr=newjava.util.Random(10);for(inti=0;i10;i++){System.out.println(r.nextInt());}}两种方式的差别在于(1)首先请打开JavaDoc，我们会看到Random类的说明：此类的实例用于生成伪随机数流，此类使用48位的种子，该种子可以使用线性同余公式对其进行修改（请参阅DonaldKnuth的《TheArtofComputerProgramming,Volume2》，第3.2.1