2013年07月26日

随机数的简单生成


随机数

在C语言中产生随机数都是使用rand()函数,若还想每次都生成不一样的随机数序列,我们会考虑每次使用不同的seed来生成,最常用的方式则是使用系统的time来产生不一样的种子。

srand(time(NULL)); rand();

最近在StackOverFlow上看到一个有意思的提问,如何不使用外部函数来生成随机数,意思是自己实现一个随机数生成函数,StackOverFlow遍布神人,有个大神给出了全面又不失细致的答案,对于理解随机数很有帮助。故记录下来。

典型产生一个新的伪随机数的方式都是基于之前的那个伪随机数,所以理论上这个新的随机数是确定的。大神说The onely randomness is guranteed by providing a good sedd!。只要不是非常重于安全的考虑,都可以用这种递归的思想去产生随机数。如果提供了seed,有较多的好方法去生成随机数,大神给出了个例子Linear Congruential Generator 线性同余发生器。

代码

基于前面描述的思想,大神给出了一个简单的方法来生成随机数。

long a = 25214903917; // a 和 c 的值是在java.util.Random()中真实找到的值。 
long c = 11;
long previous = 0;

void rseed(long seed){
    previous = seed;
}

long rand(){
    long r = a*previous + c; //一般只选择该值的几位
    previous = r;
    return r;
}

同样,我们需要一些初始值来赋值给seed,以产生较好的随机序列,可以通过如下几种方式:

没有一个算法能使用同样的种子在程序每次运行时而产生不同的序列,这说明,要想产生不同的序列,必须提供不同的种子,可以通过访问外部资源,例如系统环境来做为种子,进而产生较好的随机数。

总结

网上搜了下线性同余发生器的介绍,也是一个伪随机序列发生器,不同使用在密码学中,因为产生的随机数其实是可预测的。StackOverFlow上大神真多,往往能够给出一个简炼的答案,让你豁然开朗!不得不佩服国外的大神,严谨认真,都大神了还孳孳不倦的在StackOverFlow为大家排忧解难,奉献世界!

补充

最近学习了下关于随机抽取的问题,典型的例子就是[蓄水池取样问题](http://blog.csdn.net/a81895898/article/details/8039779),对于很大规模的数字,如何保证随机的选取K个数,这个规模是无法知道的。蓄水池取样就解决了如何随机的选取出K个数,也就是保证每个数被选取的概率一样。大致的思路是,选选取前K个元素放到水库中,然后对之后的每个元素i,以K/i的概率替换吊这个水库中的某一个元素。

代码如下:

Init : a reservoir with the size : k
    for i = k+1 to N
        M = random(1,i);
        if( M < k)
            SWAP(the Mth value and ith value)
    end for

现在的问题是如果数据规模特别大,那么random可能无法产生这样大的随机数。例如在windows 32位的平台,rand()函数返回的最大值RAND_MAX是32767,这个最大数是平台依赖数。对于32的系统,只能产生如此大的数,那该怎么办。换一个方式问,就是对上千万的数据中,随机产生其中的10万个数据,rand函数产生的最大随机数是32767。

这就需要拓展rand函数的使用方法。对于如何处理大的随机数,可以先参考stackoverflow上大神的回答,不得不情不自禁的强烈推荐stackoverflow网站。

int BigRand(){
    assert(INT_MAX/(RAND_MAX+1)>RAND_MAX);
    return rand() * (RAND_MAX+1) + rand();
}

就这样简单的方式解决了随机数扩展的问题。可以简单的验证,这样依然保证了每个数的随机性。

想起了陈利人老师帖出的另一个问题,大致是这样,给定一个骰子,有六个面,1,2,3,5,6,投这个骰子,那么每个数都能1/6的等概率出现,现在给定你另一个六面都没有数字的骰子,你可以在任何一面涂上1-6中的任何数,那么怎样涂保证掷两次骰子出现的所有数字和出现的概率一样。换句话说,就是扔出骰子A,B之后,它们的数字之和都是等概率的。

很显然的方法是要么每面都不涂,要么涂上三个3,三个6。这样两个骰子出现的结果分别为1/12。

这两个问题就有一定的关联性,现在是我们给出了一种能随机产生1-6数字的方法,现在要将产生的随机数范围扩大一倍,需要怎样做,依然保证每个数字是随机的,等概率产生。这两个问题不同的情况是,前者产生随机数都是用的rand函数,都是以1/RAND_MAX的概率产生一个数,而后者首先是1/6的概率产生数,然后以3/6的概率产生0,3/6的概率产生6。

这两个例子给出了很多启发,如何去用给定的随机函数去拓展随机数的范围。

前一篇: 二叉树的遍历 后一篇: 火车运煤问题