CS 115 Lab 5 Finding Pi by Monte Carlo (Team)
Due Date: Monday October 2 by the end of the lab session
Educational goals of this lab - verify that every student can
- write a loop
- call random number functions
- write an if statement
- use a counter
Use this link to submit your team result.
Use Lab 5, Code menu choices.
(80 points) Description of the Problem:
- Pi is a Greek symbol standing for an irrational number which is used
in all kinds of calculations. Its decimal representation never terminates, but
it has been calculated to 5 trillion digits!
How is it calculated? there are many different methods. One you probably
learned in grade school is 22/7 but that is not very precise.
- The Monte Carlo method is a mathematical method to get answers to questions
which are hard to solve analytically (by hand). It involves using random numbers
to simulate a situation. In the case of finding pi, the situation imagined
is throwing darts at the square in the picture below. The area of the square
is 1x1 or 1 unit. The area of the circle that is inside the square is
one fourth of the whole circle, whose area is pi units (radius = 1, so
area is pi times 1 squared = pi). So the area of the part
of the circle that is in the square is one fourth pi.
- You throw random darts at the square, by generating random numbers
between 0 and 1 for the x and y coordinates.
- How do you determine if a dart lands in the circle?
The equation for a circle like this one is x ** 2 + y ** 2 = 1.
That describes the points ON the circle. So if x ** 2 + y ** 2 is less than
1, it's inside the circle.
- If the random point generated (dart) is inside the circle, count it.
- After all the darts are thrown, find the ratio of
the number of darts inside to the number thrown. Multiply the result by 4
because we are only doing one fourth of the circle. This is your approximation to pi.
- Calculate how close the approximation is to the math library's value for pi.
- Sample run:
Enter how many darts: 3000
approximation to pi 3.1426666666666665
3.141592653589793 - 3.1426666666666665 = -0.0010740130768733813
- Another sample run:
Enter how many darts: 30000
approximation to pi 3.1506666666666665
3.141592653589793 - 3.1506666666666665 = -0.009074013076873388
- Another sample run:
Enter how many darts: 3000000
approximation to pi 3.1419866666666665
3.141592653589793 - 3.1419866666666665 = -0.0003940130768733674
- (15 points) Write a header as usual,
with team members' names, purpose, pre- and post-conditions.
Write a short design as comments that shows the loops and if's that you need.
Explain what your variables mean.
Mention what libraries you will need to import and why.
- (50 points) Implement the program.
- Once you have the basic program running, make these additions:
- Add in this line: from time import perf_counter
- Add in a call to the function - it has no arguments - just before the loop
starts and store the result in a variable.
- Add in another call to the function just after the loop finishes. Store
the result in another variable.
- The difference between the two values
is a measure of CPU time used in seconds.
Print out the difference as the number of seconds the CPU used.
Submit your finished program with the link above. Call the file monte.py.
Use the Lab 5 and Code menu choices.
- (15 points) Answer these questions by experimenting with your program.
Include the answers at the bottom of the program in a comment.
- If you run the program multiple times with the same number of darts,
do you get exactly the same approximation? why or why not?
- How many darts does it take to cause the loop to run just barely more than one second? just barely more than 10 seconds? Mention what system you are
running it on: Mac or PC, which CPU, CPU clock speed
- Does it matter if you use x ** 2 or x * x in terms of the time used? in terms of the accuracy of the approximation?
Log off properly - you don't want your account misused by someone else!
Remember NOT to leave files
on the local hard drives in this lab or anywhere else on
campus! Make sure you save your projects on a portable
storage device you take with you!