[發(fā)明專利]乘同余隨機數(shù)生成器的譜測試方法

在審

• 申請?zhí)枺?/td>: 201410598989.0
• 申請日: 2014-10-30
• 公開（公告）號: CN104714775A
• 公開（公告）日: 2015-06-17
• 發(fā)明（設(shè)計）人: 中澤宏;中澤直也
• 申請（專利權(quán)）人: 中澤宏
• 主分類號: G06F7/58
• 分類號: G06F7/58
• 代理公司: 北京潤平知識產(chǎn)權(quán)代理有限公司 11283
• 代理人: 陳瀟瀟;肖冰濱

技術(shù)領(lǐng)域

本發(fā)明涉及新的譜測試方法。目的是創(chuàng)新性地改進(jìn)這些方法為在計算機上的均勻且獨立隨機數(shù)選擇并產(chǎn)生良好的乘同余生成器。更具體地，本發(fā)明提出了自由度為L的新的譜測試，其中L≥3，并給出了具有更可靠估值，幫助(salvage)目前被忽視的優(yōu)秀的生成器，以及提供消除不適當(dāng)?shù)纳善鞯母翡J的標(biāo)準(zhǔn)。我們在本文中用(d,z,n)表示乘同余隨機數(shù)生成器，包括自然數(shù)d＞0表示模數(shù)，整數(shù)z表示乘數(shù)并與d互質(zhì)，以及整數(shù)n定義初始隨機數(shù)，也與d互質(zhì)。生成器(d,z,n)或簡化成(d,z)產(chǎn)生整數(shù)序列{n_k≡nz^k-1?mod(d)|0<n_k<d,k＝1,2,···}，作為遞歸等價關(guān)系的解

n₁:≡n?mod(d),n_k+1:≡zn_k?mod(d),0<n_k<d,k＝1,2,···。

在計算機上，(d,z,n)生成器的輸出是實數(shù)v_k:＝n_k/d，其是連續(xù)放出的，其中0<v_k<1，k＝1,2,···，作為均勻且獨立隨機數(shù)序列。

背景技術(shù)

我們首先需要的是對已有譜測試的結(jié)構(gòu)的思考。對(d,z)生成器的第L度譜測試旨在尤其評估放出的L個連續(xù)隨機數(shù)的獨立性程度。方法采用來自生成器(d,z)的L個連續(xù)整數(shù)輸出{Q_k:＝(n_k,n_k+1,···,n_k+L-1)|k＝1,2,···}，并將其認(rèn)為是L維歐幾里得空間E_L中的點?；臼聦嵤沁@些點{Q₁,Q₂,···}在由d和z確定的點陣G_L(d,z)中。更清楚地說，L個連續(xù)隨機數(shù)的點序列位于由d和z確定并表示為G_L(d,z)的點陣的點陣點中。方法很少關(guān)注而非不關(guān)注(d,z)輸出的位置選擇過程。關(guān)注點在對E_L中點陣G_L(d,z)預(yù)備的位置分布的評估，這種結(jié)構(gòu)是否足夠作為用于均勻且獨立隨機數(shù)的位置。這句話的意思通過可見示例可以清楚理解，該示例是連續(xù)2元組的(d,z)隨機數(shù)給出的歐幾里得平面E₂中的點陣G₂(d,z)。參見圖1，示出了由(d,z)生成器放出的一個周期內(nèi)的點{Q_k:＝(n_k,n_k+1)|k＝1,2,···}的圖，其中d是奇質(zhì)數(shù)，z是其原根。(d,z)的值被選得小，由此圖看被肉眼辨認(rèn)。點位于從原點O開始邊長為d的正方形C_d中；示出的外框顯示為稍大的正方形。開始的圖示出了接近由正三角形形成的所謂的三角形點陣的放出的點的整齊陣列。如果隨機數(shù)的連續(xù)2元組希望以某種隨機觀察的方式位于這些整齊分布的位置，我們沒有理由否定統(tǒng)計學(xué)假設(shè)：隨機數(shù)的連續(xù)2元組獨立且均勻出現(xiàn)。相反，看圖1的最后，點陣點的這種分布看起來聚集在彼此間有明顯大間隔的一些不同的線上。如果2元組的點出現(xiàn)在這種類型的位置，我們找到其分布的強方向相關(guān)性，暗示我們連續(xù)隨機數(shù)或其對似乎與不確定的獨立性相關(guān)。譜檢測給出數(shù)ρ₂(d,z)>1作為對(d,z)生成器的這些印象的定量評估；參見圖1，針對G₂(d,z)點陣表示的ρ＝ρ₂(d,z)，可以理解ρ從上越接近1越好。

發(fā)明內(nèi)容

我們描述本發(fā)明的新思想。我們回到L元(d,z)隨機數(shù)中出現(xiàn)的點陣結(jié)構(gòu)的數(shù)學(xué)表達(dá)，從最簡單的L＝2的情況開始。連續(xù)2元組Q_k可以便于認(rèn)為是位置行向量，Q_k:＝(nz^k-1,nz^k)＝nz^k-1e₁,e₁:＝(1,z)。Q_k的整數(shù)坐標(biāo)在不用等值以d為模的情況下被獲得。歐幾里得平面E₂中任意點(其第二坐標(biāo)等于Q_k以d為模的值)的位置向量可以通過加入向量e₂:＝(0,d)的整數(shù)倍來得到。類似地，其第一坐標(biāo)等于Q_k的坐標(biāo)以d為模的點可以通過加入向量e₁'的整數(shù)倍來得到：