CS 475 575 Slide set 4 M Overstreet Old Dominion University Spring 2005 Random Number Generators Techniques to generate random numbers very old random number tables seldom done even cheap calculators likely to rnd function though who knows how good they are observation of physical phenomena slow expensive not reproducible computer generated find a function f such that given a seed x 0 xi xi f x i 1 0 i n computer generated cont thus x1 f x 0 x 2 f x1 x3 f x 2 x 4 f x5 etc once you pick x0 everything is determined and always produces the same sequence desirable properties ideally f should be small easy to code fast reproducible produce as many values as desired infinite length is impossible why for practical and historical reasons we usually generate u 0 1 random numbers what is random suppose we have a black box which supposedly produces the digits 0 9 in random order if we turn the box on and the 1st digit is 6 is this random can t be answered not enough information randomness is a statistical property of a sequence of numbers does not depend on how numbers are generated choice of essential characteristics not scientific but no patterns tests for randomness most seem to be along the line of eliminating undesirable characteristics frequency counts about the same number in equal sized subintervals what if the box produced 100 integers but in the order 10 0 s then 10 1 s etc serial tests the pairs xi xi 1 xi xi 2 xi xi 3 etc should be uniformly distributed tests cont more tests gap test poker test coupon collector s test permutation test runs up and runs down test monkey test requirements for test have understood statistical distribution so you can measure strength of test if fail test a fail test b don t do b bad ideas VonNeumann s midsquare method 40 s 2 xn 1 middledigits x n Knuth s unpredictable code method 50 s alg with random at least hard to anticipate from reading the code iterations jumps shifts flips etc rng from Park Miller CACM 10 88 rng goals full period random efficient reproducible proposed by Lehmer in 1951 prime modulus multiplicative linear congruential generator f z a z mod m where m is prime rng more usually want a float in 0 1 so ui zi m this is good because f z 0 z 1 m 1 1 since m is prime 2 1 m ui 1 1 m i 3 randomness of ui randomness of zi is the same as the rng mod arith example 1 f z 6z mod 13 if start with z 1 get 1 6 10 8 9 2 12 7 3 5 4 11 1 if start with z 2 what happens 2 f z 7z mod 13 start with 1 to get 1 7 10 5 9 11 12 6 3 8 4 2 1 3 f z 5z mod 13 start with 1 to get 1 5 12 8 1 start with 2 to get 2 10 11 3 2 rng cont common choice for modulus is2 b why better choice is is this prime 31 2 1 2147483647 with this choice of m still need a choice for a P M recommend 16807 an efficient implementation so f z 16807 z mod 2147483647 this generator has been extensively tested theory support RNGs using number theory can ensure max period assume generator is mixed linear congruential of form i j 1 ai j c mod m here mixed means both add mult if c 0 then this is a multiplicative linear congruential generator max period 1 max period achieved by proper choice of a xc m and 0 b if m 2 c 0 longest period P is b 2 P m 4 2 provided 1 x 0 is odd 2 a 3 8k for some integer k max period 2 For m prime and c 0 longest period P m 1 provided a has the property that the smallest k integer kasuch 1 that is divisible by m is k m 1 problem maximal period not only issue Problems with serial correlation If k random numbers at a time are used to plot points in k space the points will not fill up the space but will fall in k 1 planes At most about m1 k planes Randu is an infamous example provided by IBM a 65539 c 0 m 231 See cs475 plotting Type gnuplot then at prompt type load plot triples some code randu Bad Example Do not use Returns values between 0 and 1 Depends on 32 bit representation for integers double randu seed long int seed long int a 16807 mod 2147483647 2 31 1 double dmod 2147483647 0 2 31 1 seed seed a if seed 0 seed mod return double seed dmod better code random C implementation Park Miller s random function double random seed long int seed long int a 16807 7 5 m 2147483647 2 31 1 q 127773 m a int divide r 2836 m a lo hi test double dm 2147483647 hi seed q lo seed q test a lo r hi seed test 0 test test m return double seed dm Reference Leemis chapter 2