CS61B Lecture 24 Administrative Make sure you ve sent me mail about alternative test times Today Pseudo random Numbers Chapter 11 What use are random sequences What are random sequences Pseudo random sequences How to get one Relevant Java library classes and methods Random permutations Coming Up Concurrency and synchronization Data Structures Chapter 10 and Programming Into Java Chapter 8 Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 1 Why Random Sequences Choose statistical samples Simulations Random algorithms Choosing cryptographic keys And of course games What Is a Random Sequence How about a sequence where all numbers occur with equal frequency Like 1 2 3 4 Well then how about an unpredictable sequence where all numbers occur with equal frequency Like 0 0 0 1 1 2 2 2 2 2 3 4 4 0 1 1 1 Besides what is wrong with 0 0 0 0 anyway Can t that occur by random selection Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 2 Pseudo Random Sequences Even if definable a truly random sequence is difficult for a computer or human to produce For most purposes need only a sequence that satisfies certain statistical properties even if deterministic Sometimes e g cryptography need sequence that is hard or impractical to predict Pseudo random sequence deterministic sequence that passes some given set of statistical tests For example look at lengths of runs increasing or decreasing contiguous subsequences Unfortunately statistical criteria to be used are quite involved For details see Knuth Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 3 Generating Pseudo Random Sequences Not as easy as you might think Seemingly complex jumbling methods can give rise to bad sequences Linear congruential method is a simple method that has withstood test of time X0 arbitrary seed Xi aXi 1 c mod m i 0 Usually m is large power of 2 For best results want a 5 mod 8 and a c m with no common factors This gives generator with a period of m length of sequence before repetition and reasonable potency measures certain dependencies among adjacent Xi Also want bits of a to have no obvious pattern and pass certain other tests see Knuth Java uses a 25214903917 c 11 m 248 but I haven t checked to see how good this is Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 4 What Can Go Wrong Short periods many impossible values E g a c m even Obvious patterns E g using lower 3 bits of Xi in Java s generator to get integers in range 0 to 7 By properties of modular arithmetic Xi mod 8 25214903917Xi 1 11 mod 248 mod 8 5 Xi 1 mod 8 3 mod 8 so we have a period of 8 on this generator sequences like 0 1 3 7 1 2 7 1 4 are impossible Bad potency leads to bad correlations E g Take c 0 a 65539 m 231 and make 3D points Xi S Xi 1 S Xi 2 S where S scales to a unit cube Points will be arranged in parallel planes with voids between So random points won t ever get near many points in the cube Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 5 Other Generators Additive generator Xn arbitary value n 55 Xn 24 Xn 55 mod 2e n 55 Other choices than 24 and 55 possible This one has period of 2f 255 1 for some f e Simple implementation with circular buffer i i 1 55 X i X i 31 55 Why 31 55 24 instead of 24 return X i modulo 232 where X 0 54 is initialized to some random initial seed values Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 6 Adjusting Range and Distribution Given raw sequence of numbers Xi from above methods in range e g 0 to 248 how to get uniform random integers in range 0 to n 1 If n 2k is easy use top k bits of next Xi bottom k bits not as random For other n be careful of slight biases at the ends One method used by Java for type int Random integer in the range 0 n 1 n 0 int nextInt int n i 1 if n is 2k for some k return top k bits of next Xi int MAX largest multiple of n that is 231 while Xi MAX i 1 return Xi MAX n How to get arbitrary range of integers L to U To get random float x in range 0 x d compute d nextInt 1 24 1 24 Random double a bit more complicated need two integers to get enough bits d long nextInt 1 26 27 long nextInt 1 27 1L 53 Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 7 Other Distributions Can also turn uniform random integers into arbitrary other distributions like Gaussian bell curve Example from book want integer values Xi with Pr Xi 0 1 12 Pr Xi 1 1 2 Pr Xi 2 1 3 Pr Xi 3 1 12 Legend 0 1 2 3 0 1 2 3 0 1 2 3 4 To get desired probabilities choose floating point number 0 Ri 4 and see what color you land on Easy to compute can arrange to have at most two colors between each pair of integers return Ri 1 0 v int Ri top int Ri bot Ri where v 1 0 3 0 2 0 3 0 0 1 0 3 0 top 1 2 2 1 bot 0 1 ANY 0 3 Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 8 Java Classes Math random random double in 0 1 Class java util Random a random number generator with constructors Random generator with random seed based on time Random seed generator with given starting value reproducible Methods next k k bit random integer nextInt n int in range 0 n nextLong random 64 bit integer nextBoolean nextFloat nextDouble Next random values of other primitive types nextGaussian normal distribution with mean 0 and standard deviation 1 bell curve Collections shuffle L R for list R and Random R permutes L randomly using R Last modified Mon Nov 5 10 16 05 2001 CS61B Lecture 24 9 Shuffling A shuffle is a random permutation of some sequence Obvious dumb technique for sorting N element list Generate N random numbers Attach each to one of the list elements Sort the list using random numbers as keys Can do quite a bit better void shuffle List L Random R for int i L size i 0 i 1 swap element i 1 of L with element R nextInt i of L Example Swap items 0 1 2 3 4 5 A 2 3 A 2 3 5 1 A 3 3 A 2 2 4 2 A 3 2 A 3 2 3 3 A 3 2 A 3 2 2 0 2 3 A A 3 2 1 0 …
View Full Document
Unlocking...