-
Essay / Designing a Random Number Generator - 2071
Designing a Random Number GeneratorIntroductionThe random number generator is a computational routine or physical device that produces numbers that contain no pattern. Although using computer algorithms involves adding a pattern to the resulting sequence of numbers, we focused on generating random numbers uniformly distributed between (0,1), because the same distribution can be used to get numbers from different ranges. We all know that LCG is a well-known method to give a sequence of random numbers using a linear equation, but it still has some problems. We performed 9 different tests on our RNG and arrived at quantitative results. Some of the tests performed are single level tests and others are two level tests. we would also like to say that some of these tests are Diehard tests [http://en.wikipedia.org/wiki/Diehard_tests]. Single Level Test - This is a 1st level test that observes the p-value, where p is a measure of uniformity. If the p-value is extremely close to 0 to 1, then the generator fails because it has produced a value with very high uniformity (close to 1) or it is not uniform at all. Two-Tier Test - Creation of 'N' independent copies of the base test having 'n' sample size each. So the total sample size is “N*n”. The test gives us a “p” value (Ref-http://shazam.econ.ubc.ca/intro/diehard.htm.), we would like to present here a discussion on the p value of the test. These p-values are obtained by p = F(X), where F is the assumed distribution of the sample random variable X --- often normal. But this hypothesis F is only an asymptotic approximation, for which the fit will be worst in the tails. So you shouldn't be surprised by occasional p-values close to 0 or 1, such as .0012 or .9983. When a bitstream fails really BIG you have...... middle of paper ...... utility called TestU01 which has predefined test suites for uniform random number sequences on the interval (0,1).ConclusionWe have designed an RNG which is a combination of 4 simple generators. we tested and showed that the final RNG gives a uniform distribution and passes 9 different complex tests, which suggests that the designed RNG is sufficiently random and can be used for simulation studies or other purposes. Empirical studies also prove that combining two or more simple generators, by means of simple operations such as +, -, * or (exclusive-or), provides a composite with better randomness than either other of the components [ G. Marsaglia. A Current View of Random Number Generators, 1984].References1. G. Marsaglia. A Current View of Random Number Generators, Computer Science and Statistics: 16th Interface Symposium, Atlanta, 1984.