上海交通大学交大密西根 联合学院·一 ◆ 181 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Vg101:Introduction to Computer and Programming Random Numbers Introduction to ANSI C++
Vg101: Introduction to Vg101: Introduction to Computer and Programming Computer and Programming Random Numbers Introduction to ANSI C++
Random Numbers Deterministic programs are useful,but we also want to model non-deterministic events. Computers are deterministic,for any given set of inputs we can predict the output of the program. Need some mechanism to simulate a random process, such as flipping a coin or tossing a die. Pseudo-random numbers are generated by a deterministic process,but 1)Behave like random numbers statistically 2)Are hard to predict without knowledge of the process
上海交通大学交大密西根 联合学院·一 81T UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University class RandomT class RandomT int seed; int next(); public: RandomT ({seed =(int)time(NULL);} RandomT (const int initSeed){seed initSeed;) int nextInteger (int lower,int upper); /range in [lower,upper] int nextInteger (int limit); ∥range in0,limit--l] double nextDouble(double lower,double upper); /range in [lower,upper) double nextDouble () ∥range in0,1) bool nextBoolean (double p); //Returns a random boolean,which ∥is true with probability p,where0≤p≤l
class RandomT RandomT class RandomT { int seed; …. int next(); public: RandomT () {seed = (int) time(NULL);} RandomT (const int initSeed) {seed = initSeed;} int nextInteger (int lower, int upper); // range in [lower, upper] int nextInteger (int limit); // range in [0, limit-1] double nextDouble (double lower, double upper); // range in [lower, upper) double nextDouble (); // range in [0, 1) bool nextBoolean (double p); // Returns a random boolean, which // is true with probability p, where 0 ≤p ≤1. }
上海交通大学交大密西根 ·联合学院一 UM-SJTU Joint Institute 1Ua日 181 University of Michigan Shanghal Jiao Tong University seed AND next ( That number becomes next ( 12384 the new seed, Seed 12384
seed AND next () next () • That number becomes the new seed
上海交通大学交大密西根 B 联合学院·一 ◆ 81T UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Pseudo-Random How does next ( work?It starts with a seed (0 in next ( ◆12384 this example)and applies a certain formula to Seed generate a new 0 pseudo-random number
Pseudo-Random • How does next () work? It starts with a seed (0 in this example) and applies a certain formula to generate a new pseudo-random number
上海交通大学交大密西根 联合学院·一 ◆ 81T UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Pseudo-Random The new seed is used to produce the next random number, next ( 17 which will become the next seed,and so on. The numbers that the function produces Seed appear random to the 12384 user
Pseudo-Random • The new seed is used to produce the next random number, which will become the next seed, and so on. • The numbers that the function produces appear random to the user. next ()
上海交通大学交大密西根 ·联合学院一 1811 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Initialization of a seed Another question:how does seed get initialized?There are two ways.One is to provide a default value as part of the declaration. class RandomT { int seed; int next(); public: /Constructor Functions: RandomT (){seed =(int)time(NULL);} RandomT (const int initSeed){seed initSeed;)
Initialization of a seed Initialization of a seed • Another question: how does seed get initialized? There are two ways. One is to provide a default value as part of the declaration. class RandomT { int seed; …. int next(); public: // Constructor Functions: RandomT () {seed = (int) time(NULL);} RandomT (const int initSeed) {seed = initSeed;}
上海交通大学交大密西根 联合学院·一 ◆ 1811 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Random number ranges Next (is very general function.Sometimes,we need a random distribution in certain range. Take coin flipping as an example: - if the random range defined by the system is RAND MAX then we could take the first half as HEAD and the last half as TAIL 0 RAND MAX HEAD TAIL Is it OK if we take (next ()%2)for HEAD?
Random Number Ranges Random Number Ranges • Next () is very general function. Sometimes, we need a random distribution in certain range. • Take coin flipping as an example: – if the random range defined by the system is RAND_MAX then – we could take the first half as HEAD and the last half as TAIL – Is it OK if we take (next () % 2) for HEAD? 0 RAND_MAX HEAD TAIL
上海交通大学交大密西根 联合学院·一 ◆ 181 UM-SJTU Joint Institute University of Michigan Shanghal Jiao Tong University Random number ranges Simulating a die roll? RAND_MAX 1T2T3T456 If you don't think this problem carefully, there are several things can go wrong. Let's describe the problem like this If you continuously rolling the dies,the probability you got for each fact are the same
Random Number Ranges Random Number Ranges • Simulating a die roll? • If you don’t think this problem carefully, there are several things can go wrong. • Let’s describe the problem like this – If you continuously rolling the dies, the probability you got for each fact are the same 0 RAND_MAX 1 2 3 4 56
int RollDie (void) int intDieFaceNumber; if (next (RAND MAX 6) { intDieFaceNumber 1; 》 else if (next (RAND MAX 2/ 6) { intDieFaceNumber 2； 》 else if (next ( RAND_MAX￥3/ 6) { intDieFaceNumber 3￥ } else if next (RAND MAX x/6) { intDieFaceNumber 4； 》 else if next (RAND MAX x 5/6) { intDieFaceNumber 5; 》 else { intDieFaceNumber 6; return (intDieFaceNumber);