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

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

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

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