CS61B Lecture #32Why Random Sequences?Pseudo-Random SequencesGenerating Pseudo-Random SequencesWhat Can Go Wrong?Other GeneratorsAdjusting Range and DistributionArbitrary BoundsOther DistributionsComputing Arbitrary Discrete DistributionJava ClassesShufflingRandom SelectionAlternative Selection Algorithm (Floyd)CS61B Lecture #32[NOTE: Renumbered. Used to be #31]Today:• Pseudo-random Numbers (Chapter 11)• What use are random sequences?• Whatare“random sequences”?• Pseudo-random sequences.• How to get one.• Relevant Java library classes and methods.• Random permutations.Coming Up: Concurrency and synchronization (Data Structures, Chap-ter 10, andProgramming Into Java, Chapter 9).Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 1Why Random Sequences?• Choose statistical samples• Simulations• Random algorithms• Choosing cryptographic keys• And, of course, gamesWhat Is a “Random Sequence”?• How about: “a sequence where all numbers occur with equal fre-quency”?– Like 1, 2, 3, 4, . . . ?• Well then, how about: “an unpredictable sequence where all numbersoccur 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 occurby random selection?Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 2Pseudo-Random Sequences• Even if definable, a “truly” random sequence is difficult for a com-puter (or human) to produce.• For most purposes, need only a sequence that satisfies certain sta-tistical properties, even if deterministic.• Sometimes (e.g., cryptography) need sequence that ishardorim-practicalto predict.•Pseudo-random sequence:deterministic sequence that passes somegiven set of statistical tests.• For example, look at lengths ofruns:increasing or decreasing con-tiguous subsequences.• Unfortunately, statistical criteria to be used are quite involved. Fordetails, see Knuth.Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 3Generating Pseudo-Random Sequences• Not as easy as you might think.• Seemingly complex jumbling methods can give rise to bad sequences.•Linear congruential methodis a simple method that has withstoodtest of time:X0=arbitrary seedXi= (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 commonfactors.• This gives generator with aperiod ofm (length of sequence beforerepetition), and reasonablepotency(measures certain dependenciesamong adjacentXi.)• Also want bits of a to “have no obvious pattern” and pass certainother tests (see Knuth).• Java uses a = 25214903917, c = 11, m = 248, but I haven’t checked tosee how good this is.Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 4What Can Go Wrong?• Short periods, many impossible values: E.g., a, c, m even.• Obvious patterns. E.g., using lower 3 bits of Xiin Java’s generator,to get integers in range 0 to 7. By properties of modular arithmetic,Ximod 8 = (25214903917Xi−1+ 11 mod 248) mod 8= (5(Xi−1mod 8) + 3) mod 8so we have a period of 8 on this generator; sequences like0, 1, 3, 7, 1, 2, 7, 1, 4, . . .are impossible.• Bad potency leads to bad correlations.– E.g. Takec = 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: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 5Other 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 val-ues.Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 6Adjusting Range and Distribution• Given raw sequence of numbers, Xi, from above methods in range(e.g.) 0 to248, how to get uniform random integers in range 0 ton − 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 (nis2kfor somek )returntopkbits of nextXi;int MAX =largest multiple of n that is< 231;while (Xi>= MAX)i += 1;return Xi/ (MAX/n);}Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 7Arbitrary Bounds• How to get arbitrary range of integers (L to U)?• To get random float, x in range 0 ≤ x < d, computereturn d*nextInt (1<<24) / (1<<24);• Random double a bit more complicated: need two integers to getenough bits.long bigRand = ((long) nextInt(1<<26) << 27) + (long) nextInt(1<<27);return d * bigRand / (1L << 53);Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 8Other Distributions• Can also turn uniform random integers into arbitrary other distri-butions, like Gaussian (bell-curve).• Example from book: want integer values Xiwith Pr(Xi= 0) = 1/12,Pr(Xi= 1) = 1/2, Pr(Xi= 2) = 1/3, Pr(Xi= 3) = 1/12:0 1 2 3Legend: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.Last modified: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 9Computing Arbitrary Discrete Distribution0 1 2 3 4• Easy to compute: can arrange to have at most two colors betweeneach pair of integers.return (Ri% 1.0 > v[(int) Ri])? top[(int) Ri]: bot[Ri];wherev = { 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: Fri Nov 15 01:51:08 2002 CS61B: Lecture #32 10Java Classes• Math.random(): random double in [0..1).• Class java.util.Random: a random number generator with construc-tors:Random() generator with “random” seed (based on time).Random(seed) generator with given starting value (reproducible).• Methodsnext(k) k-bit random integernextInt(n) int in range [0..n).nextLong() random 64-bit integer.nextBoolean(), nextFloat(), nextDouble() Next random values of otherprimitive types.nextGaussian() normal distribution with mean 0 and standard devia-tion 1 (“bell curve”).• Collections.shuffle(L,R) for list R and Random R permutes Lrandomly (using R).Last
View Full Document
Unlocking...