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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.