Transcript Class 7

CSci 162
Lecture 7
Martin van Bommel
Random Numbers
• Until now, all programs have behaved
deterministically - completely predictable and
repeatable based on input values
• Some applications (e.g. games) require
unpredictable behavior - nondeterministic
• One method for nondeterminism die toss where
one of several outcomes possible
Random Numbers
• Number is random if there is no way to determine
in advance what value it will have among a set of
equally probable possibilites
• E.g. on a standard unloaded die
– random number between 1 and 6 equally possible
• Cannot generate number randomly on computer
– uses deterministic behavior
Pseudo-random Numbers
• Use a deterministic procedure to generate
“random” numbers
• Numbers must appear random
– behave like random numbers statistically
– be sufficiently difficult to predict in advance
• Random numbers generated by an algorithmic
process by a computer are called pseudo-random
numbers
Pseudo-random number in C++
• <cstdlib> includes function rand and
constant RAND_MAX
• prototype int rand();
• generates pseudo-random number between 0 and
RAND_MAX, inclusive
• Value of RAND_MAX depends on system
• Ours uses 32 767 but your program should not
rely on a given value but on the symbolic constant
Using “rand” to flip a coin
• Want to use the result of rand that is a number
between 0 and RAND_MAX to generate Heads or
Tails
• Use
if (rand() <= RAND_MAX / 2)
cout << ”Heads”;
else
cout << ”Tails”;
Wrong Method to flip a coin
• Why not use:
if (rand() % 2 == 0)
cout << ”Heads”;
etc.
• No guarantee of distribution of even and odd
numbers, only even distribution along the range 0
to RAND_MAX
Using “rand” to Roll a Die
int RollDie(void)
{
if (rand() < RAND_MAX / 6)
if (rand() < RAND_MAX*2/6)
if (rand() < RAND_MAX*3/6)
if (rand() < RAND_MAX*4/6)
if (rand() < RAND_MAX*5/6)
return 6;
}
return
return
return
return
return
1;
2;
3;
4;
5;
• Unfortunately uses new value of “rand” in each
“if”, thus losing original.
Using “rand” to Roll a Die (2)
int RollDie()
{ int r = rand();
if (r < RAND_MAX / 6)
if (r < RAND_MAX*2/6)
if (r < RAND_MAX*3/6)
if (r < RAND_MAX*4/6)
if (r < RAND_MAX*5/6)
return 6;
}
return
return
return
return
return
1;
2;
3;
4;
5;
• Unfortunately RAND_MAX*2/6 gives strange value
due to integer arithmetic
• Better to use RAND_MAX/6.0*2.0
Generalize the Problem
• Want a function to choose random number between
two values, inclusive
int RandomInteger(int low, int high);
• Four-step process
1. Normalize rand to number d where 0 <= d < 1
2. Scale d by multiplying by size of desired range
3. Truncate number back to an integer
4. Translate integer so range begins at lower bound
RandomInteger
int RandomInteger(int low, int high)
{
int k;
double d;
d = rand() / ((double) RAND_MAX + 1.0);
k = (int) (d * (high - low + 1));
return (low + k);
}