Friday, March 15, 2013

Fractions that approximate pi

We all know that 22/7 is an approximation of pi, although some think that it is exactly pi. It is not, it is just close. But why do we use 22/7 when there are other fractions that approximate pi better? Let's see what some of these fractions are.

To find these fractions I've written a Python 3 program which calculates the errors of various fractions when compared to pi. It works in the following way:

First, it considers a range of denominators to use for fractions. For each denominator, the numerator which makes the fraction closest to pi is found (for example, with a denominator of 7, the closest fraction would be 22/7).

Each fraction will get a number of digits at the beginning the same as pi. We would like to find which is the closest fraction to pi which gets, say, the first 5 digits exactly like pi's. So the best fraction for every number of exact digits is found.

Approximations are only useful if they are easy to use and remember and so we will be considering different lengths of numbers when performing the above process. First we shall find the best fractions which consist of a denominator which is less than 10, then which is less than 100, then 1000, etc. in order to control the sizes of the fractions.

Here is the code:
import math
import collections
 
def closestFraction(denominator, target):
    #The closest fraction which uses a particular denominator d to a target number t requires that we find the best numerator n such that n/d = t, so n = td, the closest whole number of which is round(td)
    numerator = round(denominator*target)
    fraction = numerator/denominator
    return (numerator, denominator, fraction)
 
def closestFractions(maxDenominatorRange, target):
    fractions = []
    fractionsFound = set()
    for denominator in range(1, maxDenominatorRange):
        (numerator, denominator, fraction) = closestFraction(denominator, target)
        if fraction not in fractionsFound: #avoid different forms of the same fraction due to non-simplification
            fractionsFound.add(fraction)
            fractions.append((numerator, denominator, fraction))
    return fractions
 
print("pi =", math.pi)
print()
for maxDenominatorRange in [10, 100, 1000, 10000, 100000]:
    #Group fractions by the number of first digits which are exactly like pi's
    numFirstDigitsDict = collections.defaultdict(list)
    for (numerator, denominator, fraction) in closestFractions(maxDenominatorRange, math.pi):
        numFirstDigits = 0
        while round(fraction, numFirstDigits) == round(math.pi, numFirstDigits):
            numFirstDigits += 1
        numFirstDigits -= 1
        numFirstDigitsDict[numFirstDigits].append((numerator, denominator, fraction))
 
    #Keep only the best fraction in each first digits group
    bestNumFirstDigitsDict = dict()
    for numFirstDigits in numFirstDigitsDict:
        bestNumFirstDigitsDict[numFirstDigits] = min(numFirstDigitsDict[numFirstDigits], key=lambda x:abs(x[2] - math.pi))
 
    print("==========")
    print("Fractions with denominator less than", maxDenominatorRange)
    for numFirstDigits in bestNumFirstDigitsDict:
        (numerator, denominator, fraction) = bestNumFirstDigitsDict[numFirstDigits]
        print("Best fraction with", numFirstDigits, "starting digits like pi's (rounded):", numerator, "/", denominator, "=", fraction)
    print()

And here are the results:

pi = 3.141592653589793

==========
Fractions with denominator less than 10
Best fraction with 0 starting digits like pi's (rounded): 19 / 6 = 3.1666666666666665
Best fraction with 1 starting digits like pi's (rounded): 25 / 8 = 3.125
Best fraction with 2 starting digits like pi's (rounded): 22 / 7 = 3.142857142857143

==========
Fractions with denominator less than 100
Best fraction with 0 starting digits like pi's (rounded): 167 / 53 = 3.150943396226415
Best fraction with 1 starting digits like pi's (rounded): 195 / 62 = 3.1451612903225805
Best fraction with 2 starting digits like pi's (rounded): 311 / 99 = 3.1414141414141414

==========
Fractions with denominator less than 1000
Best fraction with 0 starting digits like pi's (rounded): 167 / 53 = 3.150943396226415
Best fraction with 1 starting digits like pi's (rounded): 412 / 131 = 3.145038167938931
Best fraction with 2 starting digits like pi's (rounded): 2975 / 947 = 3.1414994720168954
Best fraction with 3 starting digits like pi's (rounded): 3085 / 982 = 3.1415478615071284
Best fraction with 4 starting digits like pi's (rounded): 2818 / 897 = 3.141583054626533
Best fraction with 6 starting digits like pi's (rounded): 355 / 113 = 3.1415929203539825

==========
Fractions with denominator less than 10000
Best fraction with 0 starting digits like pi's (rounded): 167 / 53 = 3.150943396226415
Best fraction with 1 starting digits like pi's (rounded): 412 / 131 = 3.145038167938931
Best fraction with 2 starting digits like pi's (rounded): 15541 / 4947 = 3.1414998989286436
Best fraction with 3 starting digits like pi's (rounded): 28497 / 9071 = 3.1415499944879284
Best fraction with 4 starting digits like pi's (rounded): 26669 / 8489 = 3.1415950053009776
Best fraction with 5 starting digits like pi's (rounded): 31218 / 9937 = 3.1415920297876623
Best fraction with 6 starting digits like pi's (rounded): 355 / 113 = 3.1415929203539825

==========
Fractions with denominator less than 100000
Best fraction with 0 starting digits like pi's (rounded): 167 / 53 = 3.150943396226415
Best fraction with 1 starting digits like pi's (rounded): 412 / 131 = 3.145038167938931
Best fraction with 2 starting digits like pi's (rounded): 15541 / 4947 = 3.1414998989286436
Best fraction with 3 starting digits like pi's (rounded): 28497 / 9071 = 3.1415499944879284
Best fraction with 4 starting digits like pi's (rounded): 294069 / 93605 = 3.14159500026708
Best fraction with 5 starting digits like pi's (rounded): 198379 / 63146 = 3.1415924999208182
Best fraction with 6 starting digits like pi's (rounded): 308429 / 98176 = 3.141592649934811
Best fraction with 7 starting digits like pi's (rounded): 209761 / 66769 = 3.141592655274154
Best fraction with 8 starting digits like pi's (rounded): 208341 / 66317 = 3.1415926534674368
Best fraction with 9 starting digits like pi's (rounded): 104348 / 33215 = 3.141592653921421
Best fraction with 10 starting digits like pi's (rounded): 312689 / 99532 = 3.1415926536189365

In my opinion, the best fraction is 355/113 which is easy to remember and is accurate up to 6 digits:
pi      = 3.141592653589793
355/113 = 3.1415929203539825

Tuesday, March 12, 2013

Montecarlo method of finding the area of a circle and pi

You may know that the digits of pi look random but did you know that you can use randomness to find pi? You can actually approximate the area of any circle using random points in a method called the Montecarlo method. The principle of this method uses something called "sampling" which works as follows:

Say you want to find the number of people in a country who are female. You don't have time to check every single person so instead you take a random sample of people, say 10% of the population, and check only those. You find that 40% of the people in this sample are female so you generalize this percentage to the whole population and say that approximately 40% of the country is female. If the sample was random, this would be a reasonable approximation and this sort of thing is done all the time in surveys.

Now what we want to do is to find the area of a circle such as this:



The Montecarlo method works in the following way:

Place that circle inside a square such as this:



Keep in mind that the area of a square is easy to find. Now throw a point inside the square at random, which would result in something like this:



Now if we repeat this process with many points and count how many of the points lie inside the circle, we can approximate what fraction of the area of the square is taken by the circle by treating the points as a sample of the total infinite number of points in the square.



For example, in the above diagram there are 17 points in total but only 14 of the points lie inside the circle. So we can say that approximately 14/17 of the area inside the square is taken by the circle.

Now lets assume that we have a decent number of points and have a good approximation of the fraction of area that is taken by the circle. How can we use this fraction to find the area of the circle? Just multiply the fraction by the area in the square. Since we know the fraction of the area of the square that lies inside the circle, we can find the area of the circle by finding what this fraction of the area actually is.

So in the above example, the length of the side of the square is about 6cm, so the area of the square is 6x6 = 36cm^2, so the area of the circle is approximately 14/17 x 36 = 29.64cm^2.

In reality, since the circle has a radius which is half as big as the side of the square, its radius is 3cm, so its area is pi x 3^2 = 28.27cm^2. Not bad for a sample of 17 points which weren't exactly placed randomly.

How can this be used to find an approximation of pi? Just approximate the area of a circle of radius 1. The area would then be pi x 1^2 = pi.

Now let's use a computer to create lots of points. How can we check if a point is inside the circle using a computer? We can simply check if the distance of the point to the center of the circle is less than or equal to the radius of the circle. If the distance to the center is greater than the radius, than the point cannot be inside the circle.



We find the distance of a point to the center by using Pythagoras' theorem as follows:



Here is the Python 3 program we'll be using:
import math, random

def isPointInCircle(x, y, Cx, Cy, radius):
    return math.sqrt((x - Cx)**2 + (y - Cy)**2) <= radius

def approximateCircleArea(radius, numberOfPoints):
    squareSide = radius*2
    Cx = radius
    Cy = radius

    pointsInside = 0
    for i in range(numberOfPoints):
        x = random.random()*squareSide
        y = random.random()*squareSide

        if (isPointInCircle(x, y, Cx, Cy, radius)):
            pointsInside = pointsInside + 1

    return pointsInside / numberOfPoints * squareSide**2
and we'll be finding what the area of a circle of radius 1 is for different numbers of points. Since the radius is 1, the area should approximate pi:
Number of pointsApproximate area (should be 3.14159...)
102.4
1003.0
10003.152
100003.14
100003.14896
1000003.14112