淺談Perl的隨機(jī)數(shù)

iamlimeng

隨機(jī)性不是您所想象的那樣呆板：一些數(shù)字流要比其它一些更隨機(jī)。計(jì)算機(jī)一直是具有完全確定性的機(jī)器，所以，特別在行為隨機(jī)性方面表現(xiàn)不盡人意，因?yàn)榇_定性的機(jī)器很難實(shí)現(xiàn)隨機(jī)。事實(shí)上，（部分）隨機(jī)數(shù)真正的唯一來(lái)源涉及到測(cè)量物理現(xiàn)象，譬如，基于測(cè)量諸如原子的放射性衰變或熱輻射中的波動(dòng)之類，它可以用某些數(shù)學(xué)方面的技巧來(lái)提取純的隨機(jī)序列（或至少是偽隨機(jī)數(shù)發(fā)生器的種子）。但多數(shù)情況下，我們并不具備這樣的條件。

無(wú)須利用實(shí)際的設(shè)備，計(jì)算機(jī)程序需要隨機(jī)數(shù)時(shí)，會(huì)自己來(lái)生成這些數(shù)字。但這種計(jì)算機(jī)的決定機(jī)制使得生成隨機(jī)數(shù)的算法很困難。正是由于這樣，而使大多數(shù)程序員轉(zhuǎn)向偽隨機(jī)數(shù)。我們建立了真正調(diào)用偽隨機(jī)數(shù)生成器(PRNG)的 random() 。什么是偽隨機(jī)數(shù)生成器？假定需要生成介于 1 和 10 之間的隨機(jī)數(shù)，每一個(gè)數(shù)出現(xiàn)的幾率都是一樣的。理想情況下，應(yīng)生成 0 到 1 之間的一個(gè)值，不考慮以前值，這個(gè)范圍中的每一個(gè)值出現(xiàn)的幾率都是一樣的，然后再將該值乘以 10。請(qǐng)注意，在 0 和 1 之間有無(wú)窮多個(gè)值，而計(jì)算機(jī)不能提供這樣的精度。

為了編寫(xiě)代碼來(lái)實(shí)現(xiàn)類似于前面提到的算法，常見(jiàn)情況下，偽隨機(jī)數(shù)生成器生成 0 到 N 之間的一個(gè)整數(shù)，返回的整數(shù)再除以 N。得出的數(shù)字總是處于 0 和 1 之間。對(duì)生成器隨后的調(diào)用采用第一次運(yùn)行產(chǎn)生的整數(shù)，并將它傳給一個(gè)函數(shù)，以生成 0 到 N 之間的一個(gè)新整數(shù)，然后再將新整數(shù)除以 N 返回。這意味著，由任何偽隨機(jī)數(shù)生成器返回的數(shù)目會(huì)受到 0 到 N 之間整數(shù)數(shù)目的限制。

在大多數(shù)的常見(jiàn)隨機(jī)數(shù)發(fā)生器中，N 是 2的32次方 （大約等于 40 億），對(duì)于 32 位數(shù)字來(lái)說(shuō)，這是最大的值。換句話說(shuō)，我們經(jīng)常碰到的這類生成器能夠至多生成 40 億個(gè)可能值。而這 40 億個(gè)數(shù)根本不算大，只是指尖這么大。

偽隨機(jī)數(shù)生成器將作為“種子”的數(shù)當(dāng)作初始整數(shù)傳給函數(shù)。這粒種子會(huì)使這個(gè)球（生成偽隨機(jī)數(shù)）一直滾下去。偽隨機(jī)數(shù)生成器的結(jié)果僅僅是不可預(yù)測(cè)。由偽隨機(jī)數(shù)生成器返回的每一個(gè)值完全由它返回的前一個(gè)值所決定（最終，該種子決定了一切）。如果知道用于計(jì)算任何一個(gè)值的那個(gè)整數(shù)，那么就可以算出從這個(gè)生成器返回的下一個(gè)值。

結(jié)果，偽隨機(jī)數(shù)生成器是一個(gè)生成完全可預(yù)料的數(shù)列（稱為流）的確定性程序。一個(gè)編寫(xiě)得很好的的 PRNG 可以創(chuàng)建一個(gè)序列，而這個(gè)序列的屬性與許多真正隨機(jī)數(shù)的序列的屬性是一樣的。一方面，偽隨機(jī)數(shù)生成器有許多有用的應(yīng)用方面用途。另一方面，在那種需要不可預(yù)料性（如洗虛擬牌或加密數(shù)據(jù)）的應(yīng)用中，偽隨機(jī)數(shù)生成器很難以一種安全的方式來(lái)使用。如果知道種子和算法，就可以很容易地推算出這個(gè)序列。

基于歷史先例，PRNG 的種子通常是參照系統(tǒng)時(shí)鐘生成的。這個(gè)想法是使用系統(tǒng)時(shí)間的某一點(diǎn)來(lái)作為種子。這意味著如果能算出生成器什么時(shí)間發(fā)生，那么就可以知道由生成器生成的每一個(gè)值（包括數(shù)字出現(xiàn)的次序）。這樣的結(jié)果說(shuō)明，用時(shí)鐘播種的偽隨機(jī)數(shù)，所有結(jié)果不是不可預(yù)測(cè)的。正如我們所見(jiàn)，這個(gè)事實(shí)對(duì)于洗牌算法和密鑰有著深遠(yuǎn)的影響。

所以，不正確地使用偽隨機(jī)數(shù)生成器會(huì)導(dǎo)致驚人的安全性問(wèn)題。希望您不會(huì)發(fā)生這類問(wèn)題。

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

以上內(nèi)容摘錄自Gary McGraw & John Viega撰寫(xiě)的《使您的軟件運(yùn)行起來(lái): 擺弄數(shù)字,真正安全的軟件需要精確的隨機(jī)數(shù)生成器》，網(wǎng)址：
http://www.ibm.com/developerworks/cn/security/playing/index.html

Perl提供了內(nèi)置的隨機(jī)數(shù)生成函數(shù)rand()，調(diào)用非常方便和簡(jiǎn)單。前幾天，需要模擬一批實(shí)驗(yàn)數(shù)據(jù)，用到Perl的隨機(jī)數(shù)，發(fā)現(xiàn)了一些很有趣的現(xiàn)象。我要模擬的數(shù)據(jù)是這樣的：從10000個(gè)有編號(hào)的元素中，每次隨機(jī)抽取200個(gè)元素，允許重復(fù)，抽取1000萬(wàn)次，統(tǒng)計(jì)每個(gè)元素被抽取到的次數(shù)。

代碼如下：

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;

復(fù)制代碼

當(dāng)我在不同的時(shí)間，不同的計(jì)算機(jī)上模擬出N份數(shù)據(jù)后，發(fā)現(xiàn)一個(gè)很難解釋的現(xiàn)象，這些數(shù)據(jù)驚人地一致，分別都圍繞兩個(gè)相對(duì)集中的區(qū)間分布，在1000-1100之間斷檔。如圖：

修改一下參數(shù)，抽取次數(shù)改為100萬(wàn)次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

修改一下參數(shù)，抽取次數(shù)改為1億次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

將元素庫(kù)改為1000個(gè)，抽取次數(shù)改為100萬(wàn)次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

將元素庫(kù)改為1000個(gè)，抽取次數(shù)改為1000萬(wàn)次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

將元素庫(kù)改為1000個(gè)，抽取次數(shù)改為1億次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

理論上正常的隨機(jī)數(shù)，應(yīng)該表現(xiàn)為正態(tài)分布。從以上分布圖我們能很明顯地發(fā)現(xiàn)Perl內(nèi)置隨機(jī)數(shù)生成函數(shù)的缺陷，當(dāng)數(shù)據(jù)量達(dá)到一定規(guī)模時(shí)，它的缺陷就會(huì)表現(xiàn)得很明顯，而且是非常不安全的。但數(shù)據(jù)規(guī)模不是很大時(shí)，用內(nèi)置隨機(jī)函數(shù)是可以接受的。由此，我們可以得出結(jié)論，Perl內(nèi)置的rand()函數(shù)是經(jīng)過(guò)閹割的偽隨機(jī)數(shù)生成器。

那么Perl能不能生成相對(duì)嚴(yán)謹(jǐn)可用的隨機(jī)數(shù)呢？有，CPAN上有幾個(gè)現(xiàn)成的模塊可用：
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.
以上模塊都能生成相對(duì)可用的隨機(jī)數(shù)。我們簡(jiǎn)單用Math::Random測(cè)試一下上述問(wèn)題。代碼如下：

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;

復(fù)制代碼

元素庫(kù)為10000個(gè)，抽取次數(shù)改為100萬(wàn)次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

元素庫(kù)為10000個(gè)，抽取次數(shù)改為1000萬(wàn)次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

元素庫(kù)為10000個(gè)，抽取次數(shù)改為1億次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

元素庫(kù)為1000個(gè)，抽取次數(shù)改為100萬(wàn)次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

元素庫(kù)為1000個(gè)，抽取次數(shù)改為1000萬(wàn)次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

元素庫(kù)為1000個(gè)，抽取次數(shù)改為1億次，其他參數(shù)不變，數(shù)據(jù)分布如圖：

從數(shù)據(jù)的分布圖來(lái)看，基本符合正態(tài)分布，在不是特別高安全要求的情況下，這就是可用的隨機(jī)數(shù)生成器，盡管它還是偽隨機(jī)數(shù)生成器。

前三個(gè)模塊，生成的數(shù)據(jù)非常接近，效果相當(dāng)，第4個(gè)未測(cè)試。

我們簡(jiǎn)單測(cè)試一下它們的運(yùn)行效率。設(shè)元素庫(kù)為10000個(gè)，抽取次數(shù)為1億次，其他參數(shù)如上，生成兩組這樣的數(shù)據(jù)。在我的計(jì)算機(jī)上運(yùn)行（Intel Core i3-2130 CPU 3.40Ghz, 2GB內(nèi)存，32位 Windows 7 SP1 旗艦版， ActivePerl 5.14.2），使用內(nèi)置函數(shù)用時(shí)55秒；使用Math::Random用時(shí)262秒；Math::Random::MT用時(shí)271秒；Math::Random::MT:erl與前者相當(dāng)；Math::TrulyRandom文檔明確說(shuō)明了很慢，未測(cè)試，肯定是龜速。

以上測(cè)試，是在32位OS上的表現(xiàn)，在64位OS上肯定會(huì)有差異，但那只是精度問(wèn)題，若數(shù)據(jù)規(guī)模大到一定程度，最終的表現(xiàn)也會(huì)顯現(xiàn)同樣的規(guī)律，不過(guò)，我沒(méi)有條件來(lái)測(cè)試。

水平有限，以上測(cè)試僅供參考，不嚴(yán)謹(jǐn)之處，請(qǐng)大牛們指正。

zhlong8

默認(rèn)的 rand 只能產(chǎn)生 32768（0x7FFF） 個(gè)不同數(shù)字

zhlong8

相對(duì)你10000個(gè)數(shù)據(jù)集來(lái)說(shuō)不可能算平均分布

zhlong8

0-0x7fff 個(gè)數(shù)字分布到 10000 個(gè)區(qū)間里面需要每個(gè)除以 3.2768

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

得到的 %hash 表明每?jī)蓚�(gè)相臨數(shù)字分布比為 3:4 也就是你圖上顯示的 900 1200 兩條線的比例

zhlong8

啊不對(duì)，是4個(gè)數(shù)字一組， 4:3:3:3 的比例

iamlimeng

回復(fù) 5# zhlong8


10000個(gè)元素，每次抽200個(gè)，抽取1000萬(wàn)次，在64位計(jì)算機(jī)上表現(xiàn)正常，內(nèi)置rand()受硬件限制，如果數(shù)據(jù)規(guī)模超過(guò)這個(gè)限制，就會(huì)有問(wèn)題。rand()可能是為了保持運(yùn)算速度而實(shí)現(xiàn)的簡(jiǎn)化版隨機(jī)，這在數(shù)據(jù)規(guī)模較小的情況下是沒(méi)問(wèn)題的，超過(guò)上限，就有問(wèn)題了。

zhlong8

回復(fù) 6# iamlimeng


    樣本空間過(guò)小導(dǎo)致平均分布在 int 取整后不再是平均分布了，只有15bit的隨機(jī)數(shù)顯然無(wú)法滿足10000個(gè)可能的值。

iamlimeng

回復(fù) 7# zhlong8

應(yīng)該是rand()底層實(shí)現(xiàn)的限制導(dǎo)致的，因?yàn)橥瑯拥臈l件，用模塊生成隨機(jī)數(shù)，表現(xiàn)正常。

pitonas

回復(fù) 5# zhlong8
是4個(gè)數(shù)字一組， 4:3:3:3 的比例


怎么兩條線不是4條線, 這說(shuō)明什么呢？

zhlong8

pitonas 發(fā)表于 2013-10-17 14:24
回復(fù) 5# zhlong8
是4個(gè)數(shù)字一組， 4:3:3:3 的比例

那3個(gè)3都是900左右重合了啊，也就是上下兩個(gè)線值的比是4:3 密度比是 1:3，第6個(gè)圖也一樣是兩條線的比例是 33：32 點(diǎn)的密度是 4:1。