Transcript ppt
John Von Neumann (1903-1957) Hans Bethe: Academic seminars (10 levels) who can understand (This is sexism, my apology.) Level 1: my mother Level 2: my wife Level 7: myself Level 8: John and the Speaker Level 9: John, (the Speaker didn't) http://www.scidiv.bcc.ctc.edu/Math/vonNeumann.html The man who knew 28% of mathematics. Level 10: not even Johnny Random Numbers Generators -- John Von Neumann -- “Any one who considers arithmetical method of producing Random numbers is, of course, in a state of sin…..” “… there is no such thing as a random number – there are only methods to produce random numbers, and an arithmetical procedure is of course not such a method…” “..... a problem we suspect of being solvable by random methods may be solvable by some rigorously defined sequence….” Two dice How to use them to generate random numbers? Roll one die: 4, 3, 2, 2, 6, 3, 5, 4, 6,... Roll two dice: 4, 8, 5, 9, 10, 2, 8,... Are they really random? But, there is no die in any computer. Ludwig Wittgenstein (1889-1951) “Turing Machines are human that compute.” “In logic nothing is accidental” Image from http://www.ags.uci.edu/~bcarver/wgallery.html Using Computers Pseudo-Random numbers. A new random number will be generated based on some old numbers. The 1st one is based on a seed. X0 X1 X2 X3 Criterion Xi-1 Xi Xi+1 1. How long is the period? 2. Is that sequence sufficiently random ? Shift digits Method X0 X1 X2 X3 Xi-1 Xi Xi+1 Suppose we want to have a sequence of random numbers between 0 and 99999 12345 12345 12345 = 152399025 23990 23990 = 575520100 55201 55201 = 3047150401 Xi+1 =(Xi Xi / 100 ) mod 100,000 X mod m = the remainder of X divided by m e.g. 9 mod 5 = 4, 5 mod 2 = 1, 9 mod 3 = 0. Linear Congruential Method Let a, c, and m be integer. a : multiplier c: increment m: modulus Xi+1 =(aXi + c) mod m X mod m = the remainder of X divided by m e.g. 9 mod 5 = 4, 5 mod 2 = 1, 9 mod 3 = 0. Theorem: Xi+1 =(aXi + c) mod m The linear congruential sequence has a period of length m iff 1. c is relatively prime to m; 2. (a - 1) is a multiple of every prime p dividing m; 3. (a - 1) is a multiple of 4, if m is a multiple of 4. The first proof was due to M. Greenberger in 1961 for m = 2n ; The general case was proven by Hull and Dobell in 1962.