Algorithm for Finding Pi, in C

Date: 02/14/98 at 22:04:25
From: Guan Yang
Subject: Algorithm for finding pi, in C

Hi!

I would like to know how to implement various algorithms for finding 
pi in the C language.

Date: 02/18/98 at 22:02:41
From: Doctor Elizabeth
Subject: Re: Algorithm for finding pi, in C

Hi, Guan:

Your question is very interesting. At your age (that's 13, right?), 
such a question is actually quite advanced. 

Okay, let's see how far we can get. Following are four algorithms I 
have used to compute approximations of Pi in my C programming course, 
and I have categorized them into three groups.

1) Using series

The technique of series approximation can be very useful in computing 
the approximations of the mathematical constant Pi. One of the 
simplest series that invloves Pi is the following:

1 - 1/3 + 1/5- 1/7 + 1/9 - 1/11 +...

as the number of terms you use gets larger, the result gets nearer to 
pi/4.

But the above series converges extremely slowly - that is, you need to 
compute a HUGE number of terms to get a better result. Since I have 
done that program, I can tell you that even after the first 10,000 
terms have been evaluated, the approximation is correct to only four 
digits.

So, now let's look some other series:

1/2 + (1/2)*(1/3)*(1/2)^3 + ((1/2)*(3/4))*(1/5)*(1/2)^5 + 
((1/2)*(3/4)*(5/6))*(1/7)*(1/2)^7 +...

This one looks quite complicated, but it converges to pi/6 pretty 
quickly. The result of my program shows that I can get an answer 
correct to ten digits by using only 15 terms in the series. 

Well, then how to write a C program to compute this more efficient 
series? I'll only give you a hint here - say we are now at the 'n'th 
term in the series, break the single term to three parts, and try to 
express each of them in terms of 'n'. If you are really interested, I 
might be able to show you the whole program at some time.

2) Calculus approach

Now this is really advanced for your age. Let me try to show you how 
it works, since it's in fact not that hard to understand.

Say we have a circle, of which the radius is 2. Can you tell me what 
the area is? That's very easy, right? - it's 4Pi. Okay, now let's look 
at only one forth of it. What do we get? Pi! So, we can get an 
approximation of Pi by computing the area of a quarter circle with a 
calculus approach.

So, what do I mean by 'calculus approach' here? Well, you simply cut 
the whole area into rectangles. When the number of the rectangles gets 
really large, the difference between the total area of the rectangles 
and the actual area of the quarter circle becomes so small that people 
can just ignore it. Now, we know how to compute the area of a 
rectangle. And in this particular case, the width of the rectangles 
are all the same, that's 2 (the radius) divided by the number of 
rectangles you want to cut the area into. The length, however, varies. 
I'll leave this part for you, but here's the hint - look for right-
angle triangles. Good luck!

3) Random possibilities

Now this sounds a little strange, but let's see. Say you have a dart 
board hanging on your wall. It consists of a circle painted on a 
square backdrop. What happens if you throw a whole bunch of darts 
completely randomly, ignoring any darts that miss the board 
altogether? Some of the darts will fall inside the painted circle, but 
some will be outside the circle in the corners of the square. Because 
you threw the darts randomly, the ratio of the number of darts that 
landed inside the circle to the total number of darts hitting the 
square should be approximately equal to the ratio between the two 
areas, which would be Pi/4.

To simulate this process in a program, imagine that the dart board is 
drawn on the standard coordinate plane, with its center at the origin 
and a radius of 1 unit. The process of throwing a dart randomly at the 
square can be modeled by generating two random numbers, x and y, each 
of which lies between -1 and 1. Such an (x,y) point always lies some-
where inside the square. It lies inside the circle if x^2 + y^2 < 1.

I haven't yet done this program, but I don't think you should expect a 
close approximation using this method.

This is a pretty long answer. Hope it helps.

-Doctor Elizabeth,  The Math Forum
 http://mathforum.org/dr.math/