Random NumbersOnce upon a time . . .Computational Randomness is HardCelebrating Don’s 10000002th BirthdaySimulating a Shuffling MachineQuestion: Is this a Good Machine?Slide 7Using the RandomGenerator ClassCreating a Random GeneratorSlide 10Methods to Generate Random ValuesUsing the Random MethodsExercises: Generating Random ValuesSimulating the Game of CrapsSimulating RandomnessPseudorandom NumbersThe Random Number SeedDebugging and Random BehaviorExercise: Color Changing SquareThe javadoc Documentation SystemSample javadoc PagesSlide 22Slide 23Writing javadoc CommentsAn Example of javadoc CommentsGeometrical Approximation of PiRunning the SimulationExercise: Write PiApproximationThe EndSlide 30Random NumbersEric RobertsCS 106AJanuary 22, 2010Once upon a time . . .Computational Randomness is Hard The best known academic computer scientist at Stanford—and probably in the world—is Don Knuth, who has now been retired for many years. Over his professional life, he has won most of the major awards in the field, including the 1974 Turing Award. In 1969, Don published the first three volumes of his encyclopedic reference on computing, The Art of Computer Programming. The second volume is devoted to seminumerical algorithms and includes a 160-page chapter on random numbers whose primary message is that “it is not easy to invent a fool-proof random-number generator.”Celebrating Don’s 10000002th Birthday In January 2002, the computer science department organized a surprise birthday conference in honor of Don Knuth’s 64th birthday (which is a nice round number in computational terms). One of the speakers at the conference was Persi Diaconis, Professor of both Mathematics and Statistics, who spent the first decade of his professional life as a stage magician.At the conference, Persi described what happened when he was contacted by a Nevada casino to undertake a statistical analysis of a new shuffling machine . . .Simulating a Shuffling Machine The machine in question works by distributing a deck of cards into a set of eight bins.In phase 1, the machine moves each card in turn to a randomly chosen bin.If cards already exist in a bin, the machine randomly puts the new card either on the top or the bottom.In phase 2, the contents of the bins are returned to the deck in a random order.Question: Is this a Good Machine? •Thought experiment: What are the odds that the bottom card (the white card in the simulation) becomes the top card after the shuffling machine runs through a single cycle?•Answer: Because the bottom card is sorted last into the bins, it will be the top card in its bin half the time. If that bin is chosen last in Phase 2 (which happens one time in eight), the bottom card will end up on the top. This analysis suggests that the odds of having the bottom card become the top card are 1 in 16, which is considerably higher than 1 in 52.•Running a simulation of this machine verifies this analysis experimentally. After 52,000 trials:–The bottom card became the top card 3326 times.–The bottom card became the second card only 46 times.Random NumbersUsing the RandomGenerator Class•Before you start to write classes of your own, it helps to look more closely at how to use classes that have been developed by others. Chapter 6 illustrates the use of existing classes by introducing a class called RandomGenerator, which makes it possible to write programs that simulate random processes such as flipping a coin or rolling a die. Programs that involve random 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 in exactly the same way each time. Nondeterminism also has important 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 to create an instance of the RandomGenerator class.•In most cases, you create a new instance of a class by using the new operator, as you have already seen in the earlier chapters. From that experience, you would expect to create a RandomGenerator object by writing a declaration like this:RandomGenerator rgen = new RandomGenerator();For reasons that will be discussed in a later slide, using new is not appropriate for RandomGenerator because there should be only one random generator in an application. What you want to do instead is to ask the RandomGenerator class for a common instance that can be shared throughout all classes in your program.Creating a Random Generatorprivate RandomGenerator rgen = RandomGenerator.getInstance();•The recommended approach for creating a RandomGenerator instance is to call the getInstance method, which returns a single shared instance of a random generator. The standard form of that declaration looks like this:•This declaration usually appears outside of any method and is therefore an example of an instance variable. The keyword private indicates that this variable can be used from any method within this class but is not accessible to other classes.•When you want to obtain a random value, you send a message to 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, all you 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
View Full Document
Unlocking...