CS173: Intro to Computer Science - Estimating Pi with Monte Carlo Simulation (100 Points)
Assignment Goals
The goals of this assignment are:- To use iteration to solve problems while avoiding the need to write duplicate code
Background Reading and References
Please refer to the following readings and examples offering templates to help get you started:The Assignment
In this lab, you will use iteration to help you avoid writing (and debugging, and fixing, and maintaining) the same code over and over again. Specifically, we will estimate the value of \(\pi\) using iteratively generated random numbers.
Imagine a unit square with a circle inscribed. The diameter of the circle is 1, since the length of a side of the unit square (in which the circle is inscribed) is 1.
Question: what is the area of the square, and what is the area of the circle?
See this article for an animation showing the estimation of the value of \(\pi\) as the ratio of the number of points that fall inside of the area of the circle to the number of points that fall inside the area of the square.
What to Do
Generate 10 pairs of random numbers (x and y coordinates) between 0 and 1. Only some (or perhaps none!) of these points lie inside the circle, but all of these points lie inside the unit square. The ratio of the points inside the circle to the points inside the square should approximate the ratio of the area of the circle to the area of the square, given enough points.
\(\frac{A_{circle}}{A_{square}} = \frac{\pi \times r^{2}}{s^{2}}\)
Since we’re using a unit square with side length \(s = 1\), we know that \(r = 0.5\). This gives us the following:
\(\frac{A_{circle}}{A_{square}} = \frac{\pi \times 0.5^{2}}{1^{2}}\)
\(\frac{A_{circle}}{A_{square}} = \pi \times 0.25\)
Amazingly, the ratio of data points inside the circle to those inside the square is \(\frac{\pi}{4}\). In fact, since every data point is inside the square (because x and y are both between 0 and 1), the percentage of data points inside the unit circle will approximate \(\frac{\pi}{4}\).
We know that a point (x, y) lies within a unit circle if \(x^{2} + y^{2} \leq 1\). Thus, you can create a program with a function estimatePi that accepts a parameter that specifies the number of pairs of random numbers (x, y) to generate. Return the percentage of those random pairs that lie within the unit circle.
Call this function for various numbers of iterations (for example, 10, 100, 1000, 10000, 100000, 1000000, and 10000000), and compute the error from the actual value of \(\frac{\pi}{4}\). Now, run it a second time: do the error values change? If so, by how much?
Here is an example loop that you might include in your estimatePi function, to get you started. I recommend accepting an int parameter in estimatePi called iterations that indicates how many times to run the loop each time, as follows:
public static double estimatePi(int iterations) {
int inCircle = 0;
for(int i = 0; i < iterations; i++) {
// TODO: Compute a random x value using Math.random()
// TODO: Compute a random y value using Math.random()
// TODO: Compute x-squared and y-squared
// TODO: if x-squared added to y-squared is less than or equal to 1, increment a counter inCircle
// ... (in other words, set inCircle equal to inCircle plus 1)
}
// TODO: your estimate of pi is equal to four times the counter divided by iterations
// ... but watch out for integer division! Consider multiplying one of the integers by 1.0
// ... during the division to ensure that you use floating point values that do not round!
// ... if you get 3.0 as your estimate of pi, you might be integer dividing here by mistake.
// TODO: Return the estimate of pi
}
public static void main(String[] args) {
double piEstimate = estimatePi(1000); // use 1000 iterations this time
// TODO: Your error is Math.PI - piEstimate: print this error, your number of iterations,
// ... and your estimate of pi
// TODO: Try putting this main code into a loop of its own, that starts with 10 iterations, and
// multiplies by 10 each time through the loop, until you have performed 10000000 iterations.
// This way, you will automatically run all your trials for you!
// ... Try using a for loop that counts from i = 10 up to i = 1000000, with i*=10 to multiply i by 10
// ... all your code inside main (the call to piEstimate, and your print statements) will go inside
// ... this for loop!
}
Exporting your Project for Submission
When you’re done, write a README for your project, and save all your files, before exporting your project to ZIP. In your README, answer any bolded questions presented on this page. Here is a video tutorial describing how to write a README for your project, and how to export it.
Submission
In your submission, please include answers to any questions asked on the assignment page in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in your README file as well. Finally, include answers to the following questions:- If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
- Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
- Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
- Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
- Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).
Assignment Rubric
| Description | Pre-Emerging (< 50%) | Beginning (50%) | Progressing (85%) | Proficient (100%) |
|---|---|---|---|---|
| Algorithm Implementation (60%) | The algorithm fails on the test inputs due to major issues, or the program fails to compile and/or run | The algorithm fails on the test inputs due to one or more minor issues | The algorithm is implemented to solve the problem correctly according to given test inputs, but would fail if executed in a general case due to a minor issue or omission in the algorithm design or implementation | A reasonable algorithm is implemented to solve the problem which correctly solves the problem according to the given test inputs, and would be reasonably expected to solve the problem in the general case |
| Code Quality and Documentation (30%) | Code commenting and structure are absent, or code structure departs significantly from best practice, and/or the code departs significantly from the style guide | Code commenting and structure is limited in ways that reduce the readability of the program, and/or there are minor departures from the style guide | Code documentation is present that re-states the explicit code definitions, and/or code is written that mostly adheres to the style guide | Code is documented at non-trivial points in a manner that enhances the readability of the program, and code is written according to the style guide |
| Writeup and Submission (10%) | An incomplete submission is provided | The program is submitted, but not according to the directions in one or more ways (for example, because it is lacking a readme writeup) | The program is submitted according to the directions with a minor omission or correction needed | The program is submitted according to the directions, including a readme writeup describing the solution |
Please refer to the Style Guide for code quality examples and guidelines.