A Slice of Pi

Note: This problem is optional (ungraded) but encouraged because it's cool and is excellent practice for loops and the range function.

1) Problem Description

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!¹

2) Program Specification

Write a program that calculates an estimate of \pi using the method above, for a particular value of p_d. We recommend reading the next section before beginning work. Link to starter code file

def estimate_pi(pd):
    """
    Inputs:
        pd (int) - odd-valued discretization parameter / circle diameter

    Returns:
        Estimate for the value of pi

    """
    pass # your code here

def num_in_circle(pd):
    """
    This function will *not* be tested but it is useful for breaking your
    program down and testing a smaller piece of code!

    Inputs:
        pd (int) - odd-valued discretization parameter / circle diameter

    Returns:
        The number of squares whose center coordinates are within the circle
        with radius pd/2
    """
    pass # your code here


if __name__ == "__main__":
    # Local testing -- feel free to add your own tests as well!
    print(f"Got {estimate_pi(5)=}, Expected=3.36")
    print(f"Got {num_in_circle(5)=}, Expected=21")

3) Strategy and Design

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 pd to simply return the (x, y) pairs of all of the cells we want to check. You can test this with pd = 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 pd to return only the x values of the cells we want to check. Once you have that, how can you expand the idea to return the (x, y) pairs?
• Once you have that working, you can modify your program so that it returns 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 return that result (True or False) instead of returning the distance directly. Again, you can verify this step by making sure all the cells that are red in the pd=5 diagram above return True in your code when pd=5.
• Then you can modify your code to keep track of the number of cells within the circle and without, and to return these values once it is done considering all the cells. Again, you can check these against the drawings above for various values of pd shown above.
• Finally, you can make sure that your program only returns the value that the problem asked for.

4) Code Submission

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...

Next Exercise: What's the Difference?

Back to exercises