Associated Topics || Dr. Math Home || Search Dr. Math

### 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:

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/
```
Associated Topics:
High School Calculators, Computers
Middle School Pi

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search