Due Date: Monday March 22 by the end of the lab session

Use the Canvas link to submit your file.

Educational goals of this lab - verify that every student can

• write a loop
• call random number functions
• write an if statement
• use a counter

INSTRUCTIONS:

(90 points) Description of the Problem:

• π 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.
• 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 π, 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 π units (radius = 1, so area is π times 1 squared = π). So the area of the part of the circle that is in the square is one fourth π.
• 
• 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 π.
• Calculate how close the approximation is to the math library's value for π.
• Nice page with animation of the process

Samples

• Sample run:

  Monte Carlo Finding Pi
  
  Enter how many darts: 30000
  
  Time taken: 0.012208583000000002 seconds
  
  approximation to pi 3.136400000000000
  3.141592653589793 - 3.1364 = 0.005192653589793039
  

• Another sample run:

  Monte Carlo Finding Pi
  
  Enter how many darts: 300000
  
  Time taken: 0.12075244499999999 seconds
  approximation to pi 3.141253333333333
  3.141592653589793 - 3.1412533333333332 = 0.00033932025645988517
  

• Another sample run:

  Monte Carlo Finding Pi
  
  Enter how many darts: 3000000
  
  Time taken: 1.204751691 seconds
  approximation to pi 3.142974666666666
  3.141592653589793 - 3.1429746666666665 = -0.0013820130768733563
  

  A long sample run (500 million)

  Monte Carlo Finding Pi
  
  Enter how many darts: 500000000
  
  Time taken: 193.436071747 seconds
  or 3.0 minutes and 13.436071747 seconds
  approximation to pi 3.141637248000000
  3.141592653589793 - 3.141637248 = -4.4594410206766355e-05
  

No Test Cases on this one at this point.

The random numbers make it difficult to do this method by hand. Instead, see the Experimentation section below.

Design

• (20 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.

Implementation

• (50 points) Implement the program.
  • Implement the algorithm described above.
  • Once you have the basic program running, make these additions:
    • Add in this line: from time import process_time
    • This function process_time returns the CPU time used by the program up to the point of the call. It is part of the time library.
    • 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 between the two function calls. Print out the difference as the number of seconds the CPU used. If the seconds is more than one minute, also print out as minutes and seconds.

Experimenting

• (20 points) Answer these questions by experimenting with your program. Include the answers at the bottom of the program in a comment.
  1. If you run the program multiple times with the same number of darts, do you get exactly the same approximation? why or why not?
  2. How many darts does it take to cause the loop to run just barely more than one second? just barely more than 10 seconds? Docuemnt what system you are running it on: Mac or PC, which CPU, CPU clock speed
  3. Try the same code on the computers of every member of the team, with the same number of darts. Document the same info as the last question.
  4. 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? Try it and see!