Hi all,

First for PL... I'm wondering what alghorithms are best for counting PI... very accurate... I know about two methods:

first - easier, but I think itn't fast enough, is - divide quater of circle to n small pieces and count it... like this:

PI/4 = sum from i=0 to n of sqrt(1-(i/n)^2)/n

and as large n we take - we get better accuracy... but this isn't best I think... there is also other way:

second - needs some math to know about that... when we take Maclaurin Sequence (Taylor Sequence with base point x_0 = 0) for arcus tanges x, with range [-1;1] in point x=1 we get value of PI/4 (couse of arctg 1 = Pi/4) and when we compare it with Maclaurin Sequence we got harmonic sequence like this:

PI/4 = sum from i=0 to n of (-1)^(n-1) / (2n-1) = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ...

again - large n => acurate pi...

Same is for e... I know two methods:

first - from definition...

e = (1 + 1/n)^n

so as large n - more accurate e, and second (with Maclaurin Sequence):

e = sum from i=0 to n 1/n! = 2 + 1/2 + 1/6 + 1/24 + ...

this also looks better for me, but I want to know if there are any other methods? maybe some of them can be easier coded or are faster? (note that i should write everywhere n->infinity, but we computers can't understand this so I decided to write aproximations...) ... so how about it?

edit-----------------
thanks to vizskywalker for pointing out my typing error in Maclaurin e^x formula...

 

 

 

Reply

As far as computers go, a computer can calculate exponents very quickly, so I think the definition of e would probably be a better and faster way to calculate it. And the Maclaurin series is 2 + 1/2 + 1/6 + 1/24 + ..., not 1 + 1/2 + 1/6 + 1/24... It comes from the Maclaurin series for e^x which is the sum from 0 to infinite of 1/n! * x^n. When we want e, x is 1, and the sum becomes 1/0!*1^0 + 1/1!*1^1 + 1/2! * 1^2 + ... which is 1 + 1 + 1/2 + .... However, using the Maclaurin series is an easier way if you only need e to a certain amount of decimal places. For example, let's say we want three decimal places. Since 1/6! is .003888 with repeating 8s, and 1/7! is .001984126984126 with 984126 repeating. We do not have to take the Maclaurin series out past 7. However, this kind of situation is a lot harder to figure out using the definition.
Pi can also be calculated very precisely, although slowly, by a Maclaurin sum and other steps. The first we need is the sum for arctan(x) which is the sum of as n goes from 0 to infinity of 1/(2n+1)*x^(2n+1). Pi/4 is the sum of arctan(1/2) + arctan(1/5) + arctan(1/8). Simply multiply Pi/4 by 4 to get Pi. This method was used byStrassnisky to calculate the first 205 digits of Pi, and all but the last five were correct. The pattern of the arctangents may or may not continue, I do not know.

(The information on Pi was pulled from page 107 of A History of Pi by Petr Beckmann (yes, it is Petr not Peter))

 

 

 

Reply

yup you are right with that 2 instead of 1 - stupid error, just wrong typed number ... but about that Pi i think that I wrote right thing... that was how I got this:

first:

1 / (1+x^2) = sum {from 0 to infinity} (-1)^n * x^2n - that's easy...

second:

arctg x = integral {from 0 to x} dt/(1+t^2) =
= integral {from 0 to x} sum {from n=1 to infinity} (-1)^n * t^2n dt =
= sum {from n=0 to infinity} (-1)^n integral {from 0 to x} t^2n =
= sum {from n=0 to infinity} (-1)^n * [t^(2n+1) / (2n+1)]|{from 0 to x} =
= sum {from n=0 to infinity} (-1)^n * (x^(2n+1) / (2n+1)). - some elementary knowledge about integral of sequence...

finaly:

PI = 4 arctg1 = 4 sum {from n=1 to infinity} (-1)^n / (2n+1) = 4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - ...)

am I right? anyway - that's what I remember... I'll recheck this one more time, but I'm prety sure that this is correct... And wouldn't this be easier than calculating arctan one after another? - this is about geting most acurate values without using math libs or any other premade support like functions arctan... how do you find what I wrote? If this is correct would be this fast or slow?

Reply

Yup, everything you did looks right, sorry, I guess I didn't think that hard when I read your post. We also just started infinite series in calculus, and although I have dabbled in it on my own, I still never did integrals of one. But I would still recommend the Pi book I mentioned if you are interested in Pi. It covers how Pi was calculated from the beginning of its recorded history to the modern era ending in the 1970s. I think it even had some more accurate and/or faster routines in it than the one we listed, but I haven't really read it yet, just skimmed. Plus, it has the first 10000 digits of Pi (excluding the 3) listed, which means as far as practically anything other than finding the next digit in Pi goes, you can use that as a lookup instead of calculating.

Reply

taking ready-made large number isn't fun and it doesn't gives such satisfaction than calculating as far as you can by yourself, don't you think? maybe I'm little strange, but this is who I'm - begining mathematician Thanks for help, and pointing out this book, I'll take a look when I would have a chance...

Reply

I agree that using a ready made number isn't any fun. I rewrite every single module I use in scripting languages because using premade things isn't any fun. However, when it comes right down to it, Pi and e are included in the FPU's constants, so recreating them in a prgoram is a waste of space, and for any program designed to be distributed should simply not be done.

Reply

There are a few "simpler" ways of calculating Pi.

My favourite way of calculating Pi is putting a value of n into the following formula;

n x sin(360/2n) < pi < n x tan(360/2n)

I got that formula myself from school and is accurate if you use big values of n. n=6, will give ;
3 < pi < 3.464101615

Yet if we use 60,000 then we get;
3.141592652 < pi < 3.141592656

The reason I like this one is you can explain it to a 14 year old kid who knows trigonometry and they can see where the formula comes from. I'd post the actual derivitive we used to get it but it would look way too messy.

Reply

Wow. rkage, the formula you gave was pretty nice! I'm just a kid who doesn't know what "tan" and "sin" is, but still calculated something very close to pi with windows' calculator. It gives me some kind of joy in me...

I used 5000000000000000 for n, and got 3.1415926535897932384626433832793 < pi < 3.1415926535897932384626433832799.

Reply

yup, that one is nice Rkage, simplle and fast... I have only one question... how far can we count with it? Szupie got 30 places without 3, this is something...

If I would be writing usual program, this would be enough, I would even use some standard Pi, but what I'm writing is something different... I'm trying to collect as many methods as I can, compare them and chose two: one - fastest (to get some given result, for example 40 places), and second most accurate (when time and memory almost doesn't matter)... then take few best methods and make something like: "when we are calculating x places, we can use this method and get fastest result, but x+1 place and we cannot use this method, there comes..."

thanks for posting there, you are realy helping me

Reply

Some ways for calculating pi are sequences and so you need to get a computer program to run through the sequence until it arrives to the value you want.

Szupie calculated pi correct to thirty decimal places. That is probably accurate enough to correctly measure the circumference of a circle the size of America to the nearest centimeter. Given that we can calculate the lowst bound and highest bound, we could get a value halfway in between those so the circle would be accurate to 5mm. Which for our purposes is probably accurate enough. But for scientists who are dealing with atomic structures, their going to need a higher accuracy. But still, doing a calculation on our home computer to get such a complex value is pretty impressive.

Tecnically if we could put infinity into that equation we would get pi. But since infinity/2 is still infinity (arguably) then we can't. Still, the bigger the number, the more accurate decimal places. Just compare the tan and sin values up to the point where they differ.

Reply