|
|
发表于 2005-12-17 21:06:39
|
显示全部楼层
FC4 man rand:
***************************************************************************************
The versions of rand() and srand() in the Linux C Library use the same
random number generator as random() and srandom(), so the lower-order
bits should be as random as the higher-order bits.
***************************************************************************************
man random
***************************************************************************************
The random() function uses a non-linear additive feedback random number
generator employing a default table of size 31 long integers to return
successive pseudo-random numbers in the range from 0 to RAND_MAX. The
period of this random number generator is very large, approximately
16*((2**31)-1).
***************************************************************************************
可见Unix上随机数的实现对所生成的数随机度是相当重视的。由于电脑不可能产生真正的随机数，要保证一定的随机度可能一定要牺牲一定的性能。“The random() function uses a non-linear additive feedback random number generator employing a default table of size 31 long integers to return successive pseudo-random numbers in the range from 0 to RAND_MAX. The period of this random number generator is very large, approximately 16*((2**31)-1).”可见random的手册页上对它的性能是直言不讳的。
个人的观点来看，如果一般软件编写的话对随机数的随机程度要求是不会太高的。但是如果科研的话就令当别论了！为了最客观的模拟现实世界的物质特性，牺牲一些行能还是十分必要的。微软的随机数生成算法不知道是否有人看过，
在glibc中random函数的实现并不是线性同余算法，而是是有当seed的数组长度小于32时才会使用线性同余算法，而默认的长度是128。“By default, the package runs with 128 bytes of state information and generates far better random numbers than a linear congruential generator.”这是random.c开头的注释。个人觉得慢就慢在这个算法上，应该是为了更好的生成随机数而做的必要的牺牲，所以你的执行虽然非常的慢但是结果应该是更加正确的了。而正因为这个原因，在windows下算蒙特卡罗积分可能就不能使用rand函数了。这仅仅我的猜测，太多我就不了解了。
正好我找到的一篇文章里面有这个观点“……但是对于一些特殊目的应用这个算法生成的随机数是不行的，比如某些加密算法，蒙特卡罗积分等……”文章的原文如下：
标准库rand()函数的缺陷以及Blitz++随机数生成的简介
（newsuppy, 转载请注明出处）
当我们需要在某个任务中使用随机数，通常我们习惯于使用标准库的rand函数。像这样：srand(time(0)); // 时间种子
rand() % MAX_RAND；
标准库的rand函数使用线性同余算法，是生成速度相当快的一种随机数生成算法。在多数情况下也确实能满足我们的要求，但是对于一些特殊目的应用这个算法生成的随机数是不行的，比如某些加密算法，蒙特卡罗积分等（在.NET中创建随机密码的加密安全随机数就不能使用Random类的线性同余随机数，而要使用System.Security.Cryptography命名空间中的相关随机数生成类）。
这个线性同余算法的实现可以在很多书籍中找到。下面我给出一个The C Programming Langurage 2nd中的一个实现，这也是普遍使用的标准库随机数算法的实现：
unsigned long int next = 1;
/* rand: return pseudo-random integer on 0..32767 */
int rand(void)
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
/* srand: set seed for rand() */
void srand(unsigned int seed)
{
next = seed;
}
这个实现的问题在于rand函数return行中的那个32768，在标准库中这个数字定义为RAND_MAX宏，在VisualC++和Mingw32编译器的stdlib.h头文件（或者cstdlib)中你都可以发现RAND_MAX的值为32768。也就是说这个算法的随机数分布在0--RAND_MAX中，而在一般编译器中就是0--32768。假设你的算法需要的是300000多个的随机数，那么使用rand函数会产生重负次数近30次的随机数!
所以在这里我将简单介绍一下如何使用Blitz++库中的随机数生成类。不过在这里我不能够证明Blitz++随机数算法相对于标准库有什么优越性。Blitz++的源代码是开放的，你可以完全了解它的随机数算法的实现。
在Blitz++中随机数类组织在ranlib namespace中，使用方法也非常简单，seed成员函数种入种子后，再用random成员函数就可以了。Blitz++中包括了产生各种概率分布情况的随机数，列举如下：均匀分布(Uniform),正态分布(Normal)，指数分布(Exponential),Beta分布，Gamma分布，Χ方分布，F分布，离散均匀分布。具体地可以参考Blitz++文档的第九章。本文将会演示正态分布的随机数类。
NormalUnit<>() 标准正态分布，μ = 0, σ = 1;
Normal<>(T mean, T standardDeviation) 正态分布，N(μ, σ^2)，其中mean就是μ,standardDeviation就是σ。
Blitz++中随机数类的seed是共享的，调用一个类的seed后，其他类也同样种入了相同的种子。对于种子的来源，Blitz++文档中有这样一个注意事项:
Note: you may be tempted to seed the random number generator from a static initializer. Don't do it! Due to an oddity of C++, there is no guarantee on the order of static initialization when templates are involved. Hence, you may seed the RNG before its constructor is invoked, in which case your program will crash. If you don't know what a static initializer is, don't worry -- you're safe!
（幸运的是我也不太清楚static initializer具体指什么,:-） )
1，先来看一个标准正态分布的例子，根据3σ法则(正态分布的随机数几乎全部落在(μ-3σ,μ+3σ)中),这些随机数应该大部分落在(-3, 3)之间。
下面的程序产生10000个正态分布随机数，然后导入Matlab生成图形，横坐标是随机数的序数，纵坐标是随机数值。很显然，大部分点在3σ区间内。在区间(μ-σ,μ+σ)中数据点最密。
#include <random/uniform.h>
#include <random/normal.h>
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
using namespace ranlib;
int main()
{
const size_t MAXGEN = 10000;
NormalUnit<float> rnd;
rnd.seed(time(0));
ofstream file(c:\\\\file.txt);
// generator Normal distribution random number
for (size_t i=0; i<MAXGEN; ++i)
{
file << rnd.random() << ;
}
}
hspace=0
2，下面是一个服从于μ= 10，σ= 2的正态分布，根据3σ法则，大部分点应该落在(4,16)之间。
#include <random/uniform.h>
#include <random/normal.h>
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
using namespace ranlib;
int main()
{
const size_t MAXGEN = 1000000;
const int mu = 10;
const int sigma = 2;
Normal<float> rnd(mu,sigma);
rnd.seed(time(0));
ofstream file(c:\\\\file.txt);
// generator Normal distribution random number
for (size_t i=0; i<MAXGEN; ++i)
{
file << rnd.random() << ;
}
}
hspace=0
3，生成前述正态分布的钟型曲线（PDF）。
这里产生1M的float随机数，然后乘以10转型为整数，统计在区间0-170之间随机数出现的概率，这样再导入Matlab生成图形就是一个近似的正态分布的钟型曲线了。
#include <random/uniform.h>
#include <random/normal.h>
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
using namespace ranlib;
int main()
{
const size_t MAXGEN = 1000000;
const int mu = 10;
const int sigma = 2;
Normal<float> rnd(mu,sigma);
rnd.seed(time(0));
ofstream file(c:\\\\file.txt);
float *rndArray = new float[MAXGEN];
// generator Normal distribution random number
for (size_t i=0; i<MAXGEN; ++i)
{
rndArray = rnd.random();
}
int *rndConvertIntArray = new int[MAXGEN];
int multiple = 10;
// convert float random number to integer
for (size_t i=0; i<MAXGEN; ++i)
{
rndConvertIntArray = int(rndArray * multiple);
}
const size_t PDFSIZE = (mu + 3 * sigma) * multiple;
const size_t redundancy = 10;
int *pdf = new int[PDFSIZE+redundancy];
for (size_t i=0; i<PDFSIZE+redundancy; ++i)
{
pdf = 0;
}
// generator PDF(Probability Distribution Function), Normal distribution is a bell shape
for (size_t i=0; i<MAXGEN; ++i)
{
if (rndConvertIntArray <= PDFSIZE+redundancy-1)
{
++pdf[rndConvertIntArray];
}
}
for (size_t i=0; i<PDFSIZE+redundancy; ++i)
{
file << pdf << ;
}
delete[] rndArray;
delete[] rndConvertIntArray;
delete[] pdf;
}
钟型曲线，当然不是特别光滑(J),大部分随机数都出现在（4，16）区间内。
hspace=0
总结，Blitz++的随机数生成类应该说是值得信任的。
[参考文献]
1， 概率论与数理统计（3rd）， 浙江大学 盛骤 谢式千 潘承毅 编 高等教育出版社
2， C数值算法（2nd）， [美] William H. Press, Saul A. Teukolsky, William T. Vetterling,
Brian P. Flannery 著
傅祖芸 赵梅娜 丁岩石 等译，傅祖芸 审校
3，Matlab 6.5的文档 The MathWorks, Inc.
文章转自it.13520.org.希望对你有所帮助。我自己了解不多，就不边发表见解。随机数也是很多大牛都研究过的课题，包括Knuth在内。而且Linux下还有生成随机数的伪设备/dev/random,甚至还有很多厂商制造生成真实随机数的硬件设备等等。http://www.cs.berkeley.edu/~daw/rnd/上有大量的随机数生成的资料，多为用作加密用的，科研可能要求更高。另外，boost库里也有random的实现，不知道是否满足的你的要求。
PS：我个人对随机数并不了解，只是一下涉及到了Linux VS Windows的行能比拼的问题。所以顺便google，了一下。还下了glibc的代码。以上的证据应该能够有力的驳回上面很多有关性能差异的结论。很多Linux爱好者可以不必垂头丧气和愤愤不平了。最后送大家一句，有问题google(baidu)一下！～ :D |
|
楼主: Kyoryu
IP卡
狗仔卡
显身卡
发表于 2006-2-1 16:20:32