Eric Roberts Handout #23CS 106A January 22, 2010Random NumbersRandom NumbersEric RobertsCS 106AJanuary 22, 2010Computational Randomness is HardThe best known academic computer scientist atStanford—and probably in the world—is DonKnuth, who has now been retired for many years.Over his professional life, he has won most of themajor awards in the field, including the 1974Turing Award.In 1969, Don published the first three volumes ofhis encyclopedic reference on computing, The Artof Computer Programming. The second volume isdevoted to seminumerical algorithms and includesa 160-page chapter on random numbers whoseprimary message is that “it is not easy to invent afool-proof random-number generator.”Celebrating Don’s 10000002th BirthdayIn January 2002, the computer science departmentorganized a surprise birthday conference in honorof Don Knuth’s 64th birthday (which is a niceround number in computational terms).One of the speakers at the conference was PersiDiaconis, Professor of both Mathematics andStatistics, who spent the first decade of hisprofessional life as a stage magician.At the conference, Persi described what happenedwhen he was contacted by a Nevada casino toundertake a statistical analysis of a new shufflingmachine . . .Simulating a Shuffling MachineThe machine in questionworks by distributing adeck of cards into a set ofeight bins.In phase 1, the machinemoves each card in turn toa randomly chosen bin.If cards already exist in abin, the machine randomlyputs the new card either onthe top or the bottom.In phase 2, the contents ofthe bins are returned to thedeck in a random order.Using the RandomGenerator Class• Before you start to write classes of your own, it helps to lookmore closely at how to use classes that have been developedby others. Chapter 6 illustrates the use of existing classes byintroducing a class called RandomGenerator, which makes itpossible to write programs that simulate random processessuch as flipping a coin or rolling a die. Programs that involverandom processes of this sort are said to be nondeterministic.• Nondeterminstic behavior is essential to many applications.Computer games would cease to be fun if they behaved inexactly the same way each time. Nondeterminism also hasimportant practical uses in simulations, in computer security,and in algorithmic research.Creating a Random Generator• The first step in writing a program that uses randomness is tocreate an instance of the RandomGenerator class.• In most cases, you create a new instance of a class by usingthe new operator, as you have already seen in the earlierchapters. From that experience, you would expect to create aRandomGenerator object by writing a declaration like this:RandomGenerator rgen = new RandomGenerator();For reasons that will be discussed in a later slide, using new isnot appropriate for RandomGenerator because there shouldbe only one random generator in an application. What youwant to do instead is to ask the RandomGenerator class for acommon instance that can be shared throughout all classes inyour program.– 2 –Creating a Random Generatorprivate RandomGenerator rgen = RandomGenerator.getInstance();• The recommended approach for creating a RandomGeneratorinstance is to call the getInstance method, which returns asingle shared instance of a random generator. The standardform of that declaration looks like this:• This declaration usually appears outside of any method and istherefore an example of an instance variable. The keywordprivate indicates that this variable can be used from anymethod within this class but is not accessible to other classes.• When you want to obtain a random value, you send a messageto the generator in rgen, which then responds with the result.Methods to Generate Random ValuesThe RandomGenerator class defines the following methods:int nextInt(int low, int high)Returns a random int between low and high, inclusive.int nextInt(int n)Returns a random int between 0 and n - 1.double nextDouble(double low, double high)Returns a random double d in the range low  d < high.double nextDouble()Returns a random double d in the range 0  d < 1.boolean nextBoolean()Returns a random boolean value, which is true 50 percent of the time.boolean nextBoolean(double p)Returns a random boolean, which is true with probability p, where 0  p  1.Color nextColor()Returns a random color.Using the Random Methods• To use the methods from the previous slide in a program, allyou need to do is call that method using rgen as the receiver.• As an example, you could simulate rolling a die by callingint die = rgen.nextInt(1, 6);• Similarly, you could simulate flipping a coin like this:String flip = rgen.nextBoolean() ? "Heads" : "Tails";• Note that the nextInt, nextDouble, and nextBooleanmethods all exist in more than one form. Java can tell whichversion of the method you want by checking the number andtypes of the arguments. Methods that have the same name butdiffer in their argument structure are said to be overloaded.Exercises: Generating Random ValuesHow would you go about solving each of the following problems?1. Set the variable total to the sum of two six-sided dice.2. Flip a weighted coin that comes up heads 60% of the time.3. Change the fill color of rect to some randomly chosen color.Simulating the Game of CrapsCrapsRolling dice: 4 + 2 = 6Your point is 6.Rolling dice: 2 + 1 = 3Rolling dice: 3 + 6 = 9Rolling dice: 3 + 3 = 6You made your point. You win.public void run() { int total = rollTwoDice(); if (total == 7 || total == 11) { println("That's a natural. You win."); } else if (total == 2 || total == 3 || total == 12) { println("That's craps. You lose."); } else { int point = total; println("Your point is " + point + "."); while (true) . . . }}point total6 6Simulating Randomness• Nondeterministic behavior turns out to be difficult to achieveon a computer. A computer executes its instructions in aprecise, predictable way. If you give a computer program thesame inputs, it will generate the same outputs every time,which is not what you want in a nondeterministic program.• Given that true nondeterminism is so difficult to achieve in acomputer, classes such as RandomGenerator must insteadsimulate randomness by carrying out a deterministic processthat satisfies the following criteria:1. The values generated by that process should be difficultfor human observers to predict.2. Those