The Design Of Random Number Generation Algorithm Based On Interval Algorithm

Since the middle of the 20th century,as John von Neuman has proposed a simple random number generation algorithm,it's researched by more and more people,also has more rapid development,and plays an indispensable role in many fields.Due to the increasing demand for high quality random Numbers,various random number generators have been published.In 1997,Han and Hoshi put forward a random number generation Algorithm-Interval Algorithm.The thought is derived from Knuth and Yao,and the nature of the algorithm is interval iteration,and has a certain similarity with arithmetic coding decoding process.So far,the interval algorithm has been being improved and optimized,but still exist many problems,including the problem of high complexity,how to improve the finite precision arithmetic error problem,and so on.The main research of this paper is the interval algorithm.Based on the interval algorithm,a new random number generation algorithm is proposed in this paper.The algorithm is improved and optimized inheriting the advantages of the interval algorithm.The main contributions are as follows:1.The architecture of system is optimized.Instead of thinking about the M-ary input and M-ary output in the same way as the original interval algorithm,we would consider the simplest case-input and output are binary.This can effectively reduce the complexity of the algorithm in the operation of interval segmentation,interval amplification,and carry propagation,and improve the operation efficiency of the algorithm.In order to realize the change of the algorithm,the input and output requires a conversion module,this two modules can be realized through the form of a tree,the complexity of the whole system can be controlled in an ideal state.2.The model of the algorithm is expanded.We discuss the designing problem of random number generation in the condition which part of information of the source is leaked to the user(the leaked information is called side information),that is the user has side information.In this paper,we attempt three methods to improve the impact to the algorithm from the side information,that respectively are interval amplification,interval exchange,and random permutation,and obtain some useful results and conclusions,then put forward a basic framework of random number generation when the tester has side information,i.e.,a form of correlating the interval algorithm module and random permutation module.