Java
TOPIC 25 – LOOP APPLICATION: GRAPHICS

AP EXTRA: LOOP APPLICATION: SIMULATION & MATH PROBLEMS

AP LESSON NOTE

SIMULATING AN EVENT MANY TIMES

Computing has brought us the ability to simulate an event very very quickly and hence very often. This can be done simply by repeating a calculation many times in a loop.

CASE SCENARIO – COIN FLIP

Consider an event such as the flipping of a coin. Let's assume that there is a 50% chance of a result of HEADS and a 50% chance of a results of TAILS. A computer can easily simulate such an event by simply generating a random number. Because a computer can do this so quickly, we can simulate this millions of times in less than a second.

SOLVING MATH PROBLEMS

While some math problems require very innovative thinking, there are some math problems that simply require us to check a lot of possible values for something.

For example, proving that there is an infinite number of prime numbers requires innovative thinking. However, checking if any single number is a prime is a perfect problem for a computer as it simply has to check if the number has any divisors and it does so by checking every value that is smaller than that number.

Math problems that ask for the odds that something will happen can be solved by trying to do something over and over and over again. For example, the problem "How common are prime numbers between one million and two million?" can be attacked by randomly generating a number in that range and checking if it's a prime number or not. Then, we repeat that many times (1000 or more probably) to see how commonly we randomly chose a prime number.

PROBLEM #1

What are the odds that if we toss a coin ten times and we get heads all ten times?

MATH SOLUTION

So the math solution is simple enough here. Since the odds of rolling heads once is one half, we simply do ½ x ½ x ½ x ½ x ½ x ½ x ½ x ½ x ½ x ½ which equals 1/1024. In decimal form, that is 0.0009765625 or, just under 0.1%.

COMPUTING SOLUTION – SINGLE TEST

The following code generates 10 coin tosses and outputs the numbers of heads that were flipped.

//SINGLE TEST BELOW

int countHeads = 0;

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

if (Math.random() < 0.5)

{

countHeads++;

}

System.out.println(countHeads);

RE-WRITE

The above code can be written with a loop.

//SINGLE TEST BELOW

int countHeads = 0;

for (int toss=0; toss<10; toss++) //10 times

{

if (Math.random() < 0.5)

{

countHeads++;

}

}

System.out.println(countHeads);

REPEATING ABOVE TEST

We can place the above test inside a WHILE loop and repeat it many times – say one million times. We will keep track of the times countHeads is equal to 10 and then output that at the bottom.

int tenHeads = 0;

for (int tests=0; tests<1000000; tests++)

{

//SINGLE TEST BELOW

int countHeads = 0;

for (int toss=0; toss<10; toss++)

{

if (Math.random() < 0.5)

{

countHeads++;

}

}

if (countHeads == 10)

{

tenHeads++;

}

}

System.out.println(tenHeads + " out of 1000000");

System.out.println("Odds: " + tenHeads/1000000.0*100 + "%");

The above code outputs something like this:

951 out of 1000000

Odds: 0.0951%