A Slice of Pi

In this problem, we will consider an interesting method for approximating the value of the circle constant \pi.

Imagine that you did not know the value of \pi, but you did know the relationship between the area of a circle and \pi, specifically that:

We could then use the area equation and the following method to approximate \pi computationally. First, consider a circle inscribed in a square:

Measuring this ratio would give us a clear path to solving for \pi based on the formula above (we can just rearrange the formula to find \pi). But it turns out that the ratio itself is hard to measure. However, we can think about a way to approximate it.

To approximate this ratio, we can first cut the square up into a grid based on an odd-valued discretization parameter p_d, which tells us how many "grid cells" there should be along each axis. Below, we show this same drawing overlaid with a grid corresponding to p_d = 5:

In this view, if we label the center of the middle cell as (0,0) and assume that each cell has unit length, then we can label each cell with an (x, y) location:

We can now count up the number of squares whose center is inside or exactly on the border of the circle. To do this, we can check whether the distance from the center of the circle to the center (x, y) of a cell is less than the radius:

The number of cells satisfying that condition divided by the total number of cells in the grid approximates the ratio A_c/A_s. As we saw above, we can use that ratio to approximate \pi. As p_d changes, the ratio (in terms of number of grid cells) approaches the theoretical ratio, and so our estimate of \pi approaches the true value of \pi as well!

In the drawings below, the squares that satisfy this condition are colored in red, for p_d = 5, p_d = 13, and p_d=101, and some statistics are shown for each case. You should use these to help test your code as you work.

As you can see, as p_d increases, the shaded region appears to get closer and closer to the actual area of the circle, and our estimate gets closer and closer to \pi!¹

Write a program that prints an estimate of \pi using the method above, for a particular value of p_d. The first line in your program should define a variable p_d (with the underscore!) to contain the value of p_d to use. For example:

p_d = 5

It should print a single number representing the estimate of \pi that arises from the method above with that value of p_d. We recommend reading the next section before beginning work.

This is a complicated problem, and so it is a great opportunity to talk a bit about designing programs. Often, we can think about managing the complexity of a program by breaking the program down into steps to help make the process a little bit more manageable. Sometimes it is easier in the long run to start not by writing the problem we actually want to solve, but rather a similar, smaller problem that helps us accomplish one of the steps we're interested to solve.

In this problem, there are several things we have to do:

1. we have to consider every grid cell
2. we have to compute distances between grid cells and the center cell
3. we have to use that result to check whether the cell in question is within the circle
4. we have to keep track of how many cells are in the circle, and how many are in the square

That's quite a lot, but some of these pieces can be tackled via an iterative approach to solving this problem. One possible strategy is described below. Along the way, the section in this week's reading about debugging might come in handy.

• It might make sense to start with a program that uses p_d to simply print the (x, y) pairs of all of the cells we want to check. You can test this with p_d = 5 to make sure you get all the same coordinates from the diagram above.
  • Even this is not an easy problem! You may wish to break this down, and start by writing a program that uses p_d to print only the x values of the cells we want to check. Once you have that, how can you expand the idea to print the (x, y) pairs?
• Once you have that working, you can modify your program so that it prints not only the (x, y) pair associated with that point, but also the distance from the center to that point (which you can verify by hand).
• Then you can add the check for whether the center of the cell is within the circle or not, and print that result (True or False) instead of printing the distance directly. Again, you can verify this step by making sure all the cells that are red in the p_d=5 diagram above print True in your code when p_d=5.
• Then you can modify your code to keep track of the number of cells within the circle and without, and to print these values once it is done considering all the cells. Again, you can check these against the drawings above for various values of p_d shown above.
• Finally, you can remove all the helpful print statements that you used for debugging, and make sure that your program only prints the value that the problem asked for.

When you are confident that your program is working correctly, submit it below for checking. Note that submitting to this problem might take a long time, so make sure your code is working before you submit!

Select File  No file selected

Loading...