宗 慧，曹子寧，王?？?/p>

（南京航空航天大學計算機科學與技術學院，江蘇南京 211106）

隨機數在統計理論、科學研究和工程設計中具有重要作用［1］。盡管在真實的物理世界中可以得到隨機數，但限于生成速度和生成方法，真隨機數的獲取極為困難。隨著電子數字計算機的問世，采用算法產生隨機數成為一種行之有效的方法，所產生的這些數字稱作偽隨機數。當今隨機數在現代科學中的應用非常廣泛，如計算科學、通信、網絡安全、雷達探測、統計分析、數值模擬等領域都有大量的應用［2－3］。 然而，偽隨機數發(fā)生器的質量對這些應用的成效至關重要。因此，偽隨機數發(fā)生器質量受到科技界的關注。德國Federal Office for Information Security （Bundesamt für Sicherheit in der Informationstechnik，BSI）評估隨機生成器質量的主要準則要求所產生的序列的相同概率低，符合統計學的平均性。美國國家標準與技術研究院（National Iustitute of Standardsand Technology，NIST）側重于數學性能而制定了隨機性測試方法，主要包括對頻數、塊內頻數、矩陣秩、離散傅里葉變換以及幾種組合的測試［4］。 根據 BSI主要準則，文獻［5］利用 Monte Carlo計算值的方法建立了一種評價偽隨機數發(fā)生器質量的方法，該方法將理想π值作為標準，以實際計算出的值與其之差評價了多種偽隨機數發(fā)生器的質量。

1 面積之比——計算的基本思想

因此

含有內切圓的正方形如圖1（a）所示。如果該正方形由N2個面積為1的小正方形組成，那么正方形的面積就等于所有小正方形的面積之和，即As＝N2。

如果把圖1（a）中的每個小正方形用點來替代，如圖1（b）所示，那么點的數量之和就等于正方形的面積，如果把點看作單位1，當點足夠小，且當相鄰的兩點的距離趨于零時，那么區(qū)域內點的數量之和就可以等價于該區(qū)域的面積，以此類推，根據式（1）知：計算值時，只需要計算內切圓面積Ac與正方形面積As之比。因此，可以先將圖1（a）中的所有小正方形縮為圖1（b）中的點，當相鄰兩點的距離趨于零時，就可以用內切圓和正方形內的點分別代替式（1）中的Ac和As進行計算。這就可以在程序中方便地以點代面實現對值的計算，從而避免了程序從面的角度計算π值的困境。

圖1 以點代面的原理

定義1給定一個由均勻分布的充分多的點組成的含有內切圓的正方形，并設正方形內的點數為Xs，內切圓內的點數為 Xc，有

定理1

為了使證明簡潔，先回憶一下數學中對點、線和數軸的有關描述。

點是沒有部分的，即它只表示位置而無大小。兩個不同的點可以確定一條直線［15］。如果在直線上確定一個點O為原點，并指定一個方向為正向，則該直線為數軸，顯然數軸是由點的集合構成的。數軸上的每個點當且僅當對應一個實數。由于實數是稠密的，即任意兩個不同的實數間必存在另一個實數，所以數軸上的點是稠密的。又由于實數集是無限集，所以實數上的點集也是無限集。

證明：根據定義1，設含有內切圓的正方形的邊長為R，并構成如圖2所示的直角坐標。此時的3個點（0，0），（0，R）和（R，0）就確定了一個平面。 在向該平面內的正方形投放均勻分布的充分多的點時，就可以由點數計算值。然而，只有在這些投放的點是稠密的，即是無限時，才能得到與理論一致的值，即

圖2 邊長為R的正方形所在的平面

利用式（2）進行計算，正方形內必須具有一定的點數，才能得到滿足所要求精度的′。例如，正方形內只有100個點，顯然，此時計算出來的′與理論值的誤差很大，因此使用較少的點取代面積來計算′沒有意義。那么在正方形內投放多少個點才是有意義的呢？這是本文要解決的關鍵問題。下面就此進行討論。

定義2給定一個由102r個均勻分布的點組成的含有內切圓的正方形。稱圓內的點數為理想點數，記作XI；由該圖形求出的′稱作理想，記作I，且

定理2給定一個由102r個均勻分布的點組成的正方形，并設I與π的計算誤差為10－m，其中m＞0，有

證明：（i）假設落入正方形內點數為102r，并設

即

根據式（4），有

即

兩邊取對數，有

故

根據式（4），有

即

兩邊取對數，可得

故

根據（a）和（b），式（5）得證。

故m ＜0，與定理2所給條件矛盾。

（iii）的證明與（i）類似，略。

定理2表明了r與m之間的關系。根據定理2可知，當正方形內點的數量給定，那么I與的計算誤差就可以得到，同時I的精度也就確定了。

3 計算πI的算法設計

為了減少計算量，在算法設計時取如圖3（a）所示的含四分之一內切圓的正方形計算I值，首先在正方形內均勻地投放n2個點，這里的 n＝10r；然后統計內切圓內點的總數，最后根據式（4）計算I。

（count＝0） ∥count為內切圓內點數之和

在這個算法中采取的是利用循環(huán)結構依次統計內切圓內的所有點，如果投放的點數非常多，那么統計的點的數量也會加大，從而導致運算的時間變長，因此本文對這個算法進行了改進以縮短計算時間。如圖3（a）所示，可以統計正方形內內切圓外的灰色點的數量，記為Yc，這個點的數量是明顯少于內切圓內的點的數量Xc的，所以同樣投點的情況下，計算的次數減少了，計算的時長也縮短了，但是這種算法減少的計算次數還不是特別顯著。在此基礎上本文又做了一個改進，依然是統計 Yc，如圖 3（b）所示，正方形的對角線與內切圓的交點位于坐標（0.707 106 78n， 0.707 106 78n）處，因此只需要統計S1區(qū)域內的點數 S1＿count，而 S2區(qū)域內的點數是可以根據直接計算得到，記為S2＿count，然后可以得到 Yc＝ 2S1＿count＋S2＿count，按照這個思想設計的算法運算的次數大幅度降低，計算的時長也縮短了。

圖3 計算πI的算法設計

具體算法如下：

（S1＿count＝0） ∥S1＿count為內切圓外S1區(qū)域內點數之和

4 實驗結果與分析

依據表1可以看出：

表 1 不同的投點數對應的I值（π＝3.141 592 653 6……）

表 1 不同的投點數對應的I值（π＝3.141 592 653 6……）

注：列A表示IDEAL＿1算法實驗結果，列B表示IDEAL＿2算法實驗結果

總投點數 r m πI 計算時間／ms A B A B A B 25 000 000 3.698 970 004 3 3.093 9 3.470 8 3.140 787 040 0 3.141 254 400 0 18 4 100 000 000 4.000 000 000 0 3.395 6 3.774 3 3.141 190 520 0 3.141 424 520 0 72 15 2 500 000 000 4.698 970 004 3 4.095 6 4.095 5 3.141 512 417 6 3.141 512 401 6 1 702 394 10 000 000 000 5.000 000 000 0 4.396 8 4.396 7 3.141 552 545 6 3.141 552 541 6 6 795 1 561 250 000 000 000 5.698 970 004 3 5.095 9 5.095 9 3.141 584 635 8 3.141 584 635 4 169 707 39 047 1 000 000 000 000 6.000 000 000 0 5.397 5 5.397 5 3.141 588 649 6 3.141 588 649 3 679 234 156 640 25 000 000 000 000 6.698 970 004 3 6.096 8 6.478 9 3.141 591 853 3 3.141 592 321 6 16 794 482 3 858 138 100 000 000 000 000 7.000 000 000 0 6.397 8 6.779 7 3.141 592 253 5 3.141 592 487 5 67 405 604 15 442 081

表2 不同有效位的理想值對應的最低投點數

表2 不同有效位的理想值對應的最低投點數

總投點數 r 圓內點數 πI m 有效位6 512 704 3.406 9 5 112 486 3.140 008 205 5 2.800 1 2 45 832 900 3.830 6 35 990 287 3.141 000 198 5 3.227 3 3 1 873 158 400 4.636 3 1 471 131 781 3.141 500 005 6 4.033 2 4 2 274 380 691 025 6.178 4 1 471 131 782 3.141 590 000 0 5.576 2 5 37 471 488 988 816 6.786 9 29 430 051 739 428 3.141 592 000 0 6.184 7 6

最后本文結合表1和表2中的數據，繪制了r和m之間的關系，如圖4所示。根據該圖可以得到m值隨著r值的增長而增長。圖4中的曲線顯示，對于投點數（10r）2和精度（10－m）之間的關系，IDEAL＿1和 IDEAL＿2兩種算法的結果是一致的。

圖4 投點數（10r）2和精度（10－m）之間的關系

5 結束語

也可以用其他需要用到隨機數發(fā)生器計算的常數或諸如面積、體積之類的方法去評價偽隨機數發(fā)生器，比如e，這是一種比較簡便的方法。