Sample Project Report

Math 242 — Modern Computational Mathematics
Prof. Wright

Problem Statement

I will use the following sum formula to compute approximation of π:

π=4(1-(1/3)+(1/5)-(1/7)+(1/9)-(1/11)+…)

This formula is known as the Leibniz formula for π, and can be obtained from the Maclaurin series for the arctangent function.

I will investigate how the number of correct digits in the approximation of π depends on the number of terms used in the sum.

Implementation

First, I use a loop with a Print statement to generate the terms of the sum. This is just a warm-up that helps me write the following code correctly.

Do[Print[ (-1)^i/(2i+1) ],{i,0,5}]

Seeing that the terms above are correct, I add them up and multiply by 4. I put this code in a module that accepts the number of terms n as an argument and returns the sum.

computeSum[n_]:=Module[{sum=0},
Do[sum+=(-1)^i/(2i+1),{i,0,n-1}];
4*sum
]

Note that computeSum returns a fraction, which we can convert to a decimal number:

computeSum[100]

N[computeSum[1000],50]

Counting Correct Digits

To find the number of correct digits past the decimal point, I use another module. This module also requires a parameter n that specifies the number of terms of the sum to use:

correctDigits[n_]:=Module[{approx,i=0},
approx=computeSum[n];
While[ RealDigits[approx,10,1,i][[1,1]]==RealDigits[Pi,10,1,i][[1,1]],i--];
-i-1 (* the number of correct digits after the decimal point *)
]

I will check to make sure that correctDigits works. The sum with 800 terms has two correct digits after the decimal:

computeSum[800] //N

correctDigits[800]

The sum with 5000 terms has three correct digits after the decimal:

computeSum[5000] //N

correctDigits[5000]

Now I will plot of the number of correct digits for various values of n. I will let n take values from 100 to 2000, with a step size of 100.

nDigits=Table[{n,correctDigits[n]},{n,100,2000,100}]

ListPlot[nDigits,AxesLabel->{"terms in sum","correct digits"}]

We see the number of digits increase at about n=700 and again at about n=1700. Let’s collect more data. We’ll try n from 200 to 200,000, with a step size of 200.

nDigits=Table[{n,correctDigits[n]},{n,200,200000,200}];

This took a almost an hour to run! Now for a plot:

ListPlot[nDigits,AxesLabel->{"terms in sum","correct digits"}]

We see the number of digits increases to 4 somewhere around 10,000 terms. Let’s find the data point where the increase occurs:

nDigits[[50;;60]]

We have found increases in the number of digits increases by one at about n=700, n=1700, and n=10800. Since we need to compute more than ten thousand terms to get only 4 correct digits, this does not seem to be a very efficient method of computing digits of π.

Runtime

How long does it take computeSum to run? Here is a module that returns the number of seconds required to compute the sum using n terms.

runtime[n_]:=Module[{},
Timing[computeSum[n]][[1]]
]

Now we will make a plot of runtime vs number of terms.

times=Table[{n,runtime[n]},{n,1000,100000,1000}];

ListPlot[times,AxesLabel->{"number of terms","time (seconds)"}]

It looks like the runtime might be increasing quadratically with the number of terms.

Discussion

Conclusions and Conjectures

As shown in the plots above, the number of correct digits increases by one at about  n=700, n=1700, and n=10800.  It looks like computing each additional digit of π requires more than double as many terms as the previous digit. I conjecture that this pattern holds as n increases, though I only tested values of n up to 200,000.

Thus, the Leibniz sum formula converges very slowly to π. This does not seem to be a practical way of computing lots of digits of π.

Limitations and Extensions

My method of running computeSum[n] for various value of n is not a great way of figuring out how many terms are required to obtain a desired number of digits of π. For example, I would have a hard time predicting how large n should be in order to get ten correct digits of π.  Perhaps this could be studied theoretically (rather than computationally) using results about rates of convergence of infinite series.

Furthermore, such n might be quite large and my computation for that n might take a very long time. I found that my computation takes more than 2.5 seconds when n=100000, and the runtime seems to increase quadratically with n. This suggests that if I multiply n by ten, my computation time may increase by a factor of 100, which seems undesirable.

As an extension for future work, I would like to compare the Leibniz sum with other methods of computing digits of π. I would like to find methods that compute digits of π much more quickly than the Leibniz sum formula.