浅谈Perl的随机数

iamlimeng

随机性不是您所想象的那样呆板：一些数字流要比其它一些更随机。计算机一直是具有完全确定性的机器，所以，特别在行为随机性方面表现不尽人意，因为确定性的机器很难实现随机。事实上，（部分）随机数真正的唯一来源涉及到测量物理现象，譬如，基于测量诸如原子的放射性衰变或热辐射中的波动之类，它可以用某些数学方面的技巧来提取纯的随机序列（或至少是伪随机数发生器的种子）。但多数情况下，我们并不具备这样的条件。

无须利用实际的设备，计算机程序需要随机数时，会自己来生成这些数字。但这种计算机的决定机制使得生成随机数的算法很困难。正是由于这样，而使大多数程序员转向伪随机数。我们建立了真正调用伪随机数生成器(PRNG)的 random() 。什么是伪随机数生成器？假定需要生成介于 1 和 10 之间的随机数，每一个数出现的几率都是一样的。理想情况下，应生成 0 到 1 之间的一个值，不考虑以前值，这个范围中的每一个值出现的几率都是一样的，然后再将该值乘以 10。请注意，在 0 和 1 之间有无穷多个值，而计算机不能提供这样的精度。

为了编写代码来实现类似于前面提到的算法，常见情况下，伪随机数生成器生成 0 到 N 之间的一个整数，返回的整数再除以 N。得出的数字总是处于 0 和 1 之间。对生成器随后的调用采用第一次运行产生的整数，并将它传给一个函数，以生成 0 到 N 之间的一个新整数，然后再将新整数除以 N 返回。这意味着，由任何伪随机数生成器返回的数目会受到 0 到 N 之间整数数目的限制。

在大多数的常见随机数发生器中，N 是 2的32次方 （大约等于 40 亿），对于 32 位数字来说，这是最大的值。换句话说，我们经常碰到的这类生成器能够至多生成 40 亿个可能值。而这 40 亿个数根本不算大，只是指尖这么大。

伪随机数生成器将作为“种子”的数当作初始整数传给函数。这粒种子会使这个球（生成伪随机数）一直滚下去。伪随机数生成器的结果仅仅是不可预测。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定（最终，该种子决定了一切）。如果知道用于计算任何一个值的那个整数，那么就可以算出从这个生成器返回的下一个值。

结果，伪随机数生成器是一个生成完全可预料的数列（称为流）的确定性程序。一个编写得很好的的 PRNG 可以创建一个序列，而这个序列的属性与许多真正随机数的序列的属性是一样的。一方面，伪随机数生成器有许多有用的应用方面用途。另一方面，在那种需要不可预料性（如洗虚拟牌或加密数据）的应用中，伪随机数生成器很难以一种安全的方式来使用。如果知道种子和算法，就可以很容易地推算出这个序列。

基于历史先例，PRNG 的种子通常是参照系统时钟生成的。这个想法是使用系统时间的某一点来作为种子。这意味着如果能算出生成器什么时间发生，那么就可以知道由生成器生成的每一个值（包括数字出现的次序）。这样的结果说明，用时钟播种的伪随机数，所有结果不是不可预测的。正如我们所见，这个事实对于洗牌算法和密钥有着深远的影响。

所以，不正确地使用伪随机数生成器会导致惊人的安全性问题。希望您不会发生这类问题。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

以上内容摘录自Gary McGraw & John Viega撰写的《使您的软件运行起来: 摆弄数字,真正安全的软件需要精确的随机数生成器》，网址：
http://www.ibm.com/developerworks/cn/security/playing/index.html

Perl提供了内置的随机数生成函数rand()，调用非常方便和简单。前几天，需要模拟一批实验数据，用到Perl的随机数，发现了一些很有趣的现象。我要模拟的数据是这样的：从10000个有编号的元素中，每次随机抽取200个元素，允许重复，抽取1000万次，统计每个元素被抽取到的次数。

代码如下：

1. #!/usr/bin/perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. 
   
6. my $rand = 10000;
   
7. my %count = ();
   
8. for (1..10000000) {
   
9.         $count{int rand($rand)}++;
   
10. }
    
11. open(FH,">rand.xls");
    
12. for (0..$rand-1) {
    
13.         $count{$_} = 0 if (!$count{$_});
    
14.         print FH "$count{$_}\n";
    
15. }
    
16. close FH;

复制代码

当我在不同的时间，不同的计算机上模拟出N份数据后，发现一个很难解释的现象，这些数据惊人地一致，分别都围绕两个相对集中的区间分布，在1000-1100之间断档。如图：

修改一下参数，抽取次数改为100万次，其他参数不变，数据分布如图：

修改一下参数，抽取次数改为1亿次，其他参数不变，数据分布如图：

将元素库改为1000个，抽取次数改为100万次，其他参数不变，数据分布如图：

将元素库改为1000个，抽取次数改为1000万次，其他参数不变，数据分布如图：

将元素库改为1000个，抽取次数改为1亿次，其他参数不变，数据分布如图：

理论上正常的随机数，应该表现为正态分布。从以上分布图我们能很明显地发现Perl内置随机数生成函数的缺陷，当数据量达到一定规模时，它的缺陷就会表现得很明显，而且是非常不安全的。但数据规模不是很大时，用内置随机函数是可以接受的。由此，我们可以得出结论，Perl内置的rand()函数是经过阉割的伪随机数生成器。

那么Perl能不能生成相对严谨可用的随机数呢？有，CPAN上有几个现成的模块可用：
1、Math::Random: Math::Random is a Perl port of the C version of randlib, which is a suite of routines for generating random deviates.
2、Math::Random::MT: The Mersenne Twister PRNG.
3、Math::Random::MT:erl: Pure Perl Mersenne Twister Random Number Generator.
4、Math::TrulyRandom：Perl interface to a truly random number generator function. The random numbers take a long time (in computer terms) to generate, so are only really useful for seeding pseudo random sequence generators.
以上模块都能生成相对可用的随机数。我们简单用Math::Random测试一下上述问题。代码如下：

1. #!/usr/bin/perl
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. use Math::Random qw(random_uniform_integer);
   
6. 
   
7. my $rand = 10000;
   
8. my %count = ();
   
9. for (1..10000000) {
   
10.         my $no = random_uniform_integer(1, 0, $rand);
    
11.         $count{$no}++;
    
12. }
    
13. open(FH,">rand.xls");
    
14. for (0..$rand-1) {
    
15.         $count{$_} = 0 if (!$count{$_});
    
16.         print FH "$count{$_}\n";
    
17. }
    
18. close FH;

复制代码

元素库为10000个，抽取次数改为100万次，其他参数不变，数据分布如图：

元素库为10000个，抽取次数改为1000万次，其他参数不变，数据分布如图：

元素库为10000个，抽取次数改为1亿次，其他参数不变，数据分布如图：

元素库为1000个，抽取次数改为100万次，其他参数不变，数据分布如图：

元素库为1000个，抽取次数改为1000万次，其他参数不变，数据分布如图：

元素库为1000个，抽取次数改为1亿次，其他参数不变，数据分布如图：

从数据的分布图来看，基本符合正态分布，在不是特别高安全要求的情况下，这就是可用的随机数生成器，尽管它还是伪随机数生成器。

前三个模块，生成的数据非常接近，效果相当，第4个未测试。

我们简单测试一下它们的运行效率。设元素库为10000个，抽取次数为1亿次，其他参数如上，生成两组这样的数据。在我的计算机上运行（Intel Core i3-2130 CPU 3.40Ghz, 2GB内存，32位 Windows 7 SP1 旗舰版， ActivePerl 5.14.2），使用内置函数用时55秒；使用Math::Random用时262秒；Math::Random::MT用时271秒；Math::Random::MT:erl与前者相当；Math::TrulyRandom文档明确说明了很慢，未测试，肯定是龟速。

以上测试，是在32位OS上的表现，在64位OS上肯定会有差异，但那只是精度问题，若数据规模大到一定程度，最终的表现也会显现同样的规律，不过，我没有条件来测试。

水平有限，以上测试仅供参考，不严谨之处，请大牛们指正。

zhlong8

默认的 rand 只能产生 32768（0x7FFF） 个不同数字

zhlong8

相对你10000个数据集来说不可能算平均分布

zhlong8

0-0x7fff 个数字分布到 10000 个区间里面需要每个除以 3.2768

for (0 .. 0x7fff) { my $n = int ($_ / 3.2768); $hash{$n} ++ }

得到的 %hash 表明每两个相临数字分布比为 3:4 也就是你图上显示的 900 1200 两条线的比例

zhlong8

啊不对，是4个数字一组， 4:3:3:3 的比例

iamlimeng

回复 5# zhlong8


10000个元素，每次抽200个，抽取1000万次，在64位计算机上表现正常，内置rand()受硬件限制，如果数据规模超过这个限制，就会有问题。rand()可能是为了保持运算速度而实现的简化版随机，这在数据规模较小的情况下是没问题的，超过上限，就有问题了。

zhlong8

回复 6# iamlimeng


    样本空间过小导致平均分布在 int 取整后不再是平均分布了，只有15bit的随机数显然无法满足10000个可能的值。

iamlimeng

回复 7# zhlong8

应该是rand()底层实现的限制导致的，因为同样的条件，用模块生成随机数，表现正常。

pitonas

回复 5# zhlong8
是4个数字一组， 4:3:3:3 的比例


怎么两条线不是4条线, 这说明什么呢？

zhlong8

pitonas 发表于 2013-10-17 14:24
回复 5# zhlong8
是4个数字一组， 4:3:3:3 的比例

那3个3都是900左右重合了啊，也就是上下两个线值的比是4:3 密度比是 1:3，第6个图也一样是两条线的比例是 33：32 点的密度是 4:1。