Donald Knuth – The Art of Computer ProgrammingMinimal StandardLehmer’s AlgorithmThree Issues for Implementing a Lehmer GeneratorThe MultiplierImplementationConclusionsDistributed Simulation – Random Number Generators 1Donald Knuth – The Art of Computer Programming• http://www-cs-faculty.stanford.edu/~knuth/• “Look at the subroutine library of each computer installation in your organization, and replace the random number generators by good ones. Try to avoid being too shocked at what you find.”• Many random number generators have been written, most of them have demonstrably non-random characteristics, some are embarrassingly bad.Distributed Simulation – Random Number Generators 2Minimal Standard• Multiplicative linear congruential generator with multiplier 16807 and prime modulus 231–1. • Objective: a virtually infinite sequence of statistically independent random numbers uniformly distributed between 0 and 1.• D.H. Lehmer produced an algorithm in 1951 that is satisfactory under some conditions.Distributed Simulation – Random Number Generators 3Lehmer’s Algorithm• Two parameters, a and m. • “Prime Modulus Mulitplicative Linear Congruential Generator”• Initial seed• deterministic versus random• full period versus small period behavior• The Mersenne Prime231– 1 = 2147483647Distributed Simulation – Random Number Generators 4Three Issues for Implementing a Lehmer Generator1. Full period periodicity2. Randomness• See Chapter 43. Implementation• evaluating f(z) = az mod m efficiently and correctly for all valuesDistributed Simulation – Random Number Generators 5The MultiplierThe multiplier a = 75= 16807 was first suggested by Lewis, Goodman and Miller in 1969 [27], based largely on the fact that f(z) = 168072 mod 2147483645 is a full period generating function.Distributed Simulation – Random Number Generators 6Implementation• Maxint and oveflows• Check for correctness and not randomnessDistributed Simulation – Random Number Generators 7Conclusions• Many computer scientists will never have more than an occasional need to use a random number generator.• And on those occasions the statistical goodness of the random numbers they generate may not be of paramount importance.• For some of us, however, convenient and frequent access to a verifiably good random number generator is fundamentally important. • If you have need for a random number generator, particularly one that will port to a wide variety of systems, and if you are not a specialist in random number generation and do not want to become one, use the minimal standard. • It should not be presumed that it is easy to write a better