基于區(qū)間算法的隨機(jī)數(shù)生成算法的設(shè)計.pdf

1、20世紀(jì)中葉以來，隨著John von Neuman最早提出一種簡單的隨機(jī)數(shù)生成算法，其被越來越多的人所研究，發(fā)展也愈加迅速，并且在眾多領(lǐng)域中都發(fā)揮著不可或缺的作用。由于人們對高質(zhì)量隨機(jī)數(shù)的需求的增加，各種隨機(jī)數(shù)生成器相繼問世。1997年，Han和Hoshi提出了一種隨機(jī)數(shù)生成的算法——區(qū)間算法（Interval Algorithm）。該算法的思想源于Knuth和Yao，算法的本質(zhì)是區(qū)間迭代，與算術(shù)編碼的編解碼過程有一定相似性。到現(xiàn)在為

2、止，區(qū)間算法一直在被改進(jìn)和優(yōu)化，但還是存在許多問題，包括區(qū)間算法復(fù)雜性過高的問題，有限精度運算誤差如何改善的問題，等等。
　　本文主要研究的就是區(qū)間算法，以區(qū)間算法為基礎(chǔ)，提出了一種新的隨機(jī)數(shù)生成算法。該算法在繼承區(qū)間算法的優(yōu)點的基礎(chǔ)上，對算法進(jìn)行了改進(jìn)和優(yōu)化，主要貢獻(xiàn)如下:
　　1.優(yōu)化了系統(tǒng)的體系結(jié)構(gòu)。本文不再如原區(qū)間算法那樣考慮M進(jìn)制的輸入和輸出，而是直接考慮輸入和輸出都是二元的情況。這么做可以有效減小算法在進(jìn)行區(qū)間分

3、割，區(qū)間放大，進(jìn)位傳送等操作時的復(fù)雜性，提高算法的運行效率。為了實現(xiàn)算法的這一改變，輸入和輸出就需要一個轉(zhuǎn)換模塊，兩個模塊則可以通過一棵樹的形式來實現(xiàn)，整個系統(tǒng)的復(fù)雜性就可以控制在一個理想的狀態(tài)。
　　2.拓展了算法的模型。本文探討了信源的部分信息通過泄密信道泄露給隨機(jī)數(shù)的使用者的情況下（泄露的信息稱為邊信息），即使用者有邊信息的情況下隨機(jī)數(shù)生成器的設(shè)計問題。本文嘗試了三種方法來改善邊信息對算法帶來的影響，分別為區(qū)間放大，區(qū)間交換