How is pi calculated on computers?

[Nacelunk]

So, that's the question.

[NeonBlack]

Here is one way:

[math]\frac{\pi^2}{6} = \sum_{n=1}^{\infty}\frac{1}{n^2}[/math]

 

In this way, pi can be approximated by a very large n.

[Freeman]

Pi is exactly three! :-D

 

[math]

\frac{\pi}{4} = \sum_{n=0}^{\infty} \frac{(-1)^{n}}{2n+1}

[/math]

or

[math]

\prod_{n=1}^{\infty} \frac{4n^2}{4n^2-1} = \frac{\pi}{2}

[/math]

[woelen]

Try this !

 

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}

[RyanJ]

http://crd.lbl.gov/~dhbailey/pi/piqp.c

 

^ Its a bit more complex and Woelen's and I was going to write one for that formula mysqlf untill I found the author had already written one

 

Cheers,

 

Ryan Jones

[ecoli]

it can't be calculated, but it can be approximated (because it's an infinately large number, you can't get an exact value)

[RyanJ]

it can't be calculated, but it can be approximated (because it's an infinately large number, you can't get an exact value)

 

Unless you happen to have a quantim computer handy... joking aside, you are 100% correct. The formula for the code in the link I posed was actually an infininte seriese (Found on the website too)...

 

 

*Off topic*

Does anyone happen to know what the current Pi calculation record standards at by the way?

 

Cheers,

 

Ryan Jones

[ecoli]

no, not even with a quantum computer. you would (theoretically) be able to get a larger calculation with a Quantum computer, but infinate means infinate.

[woelen]

http://crd.lbl.gov/~dhbailey/pi/piqp.c

 

^ Its a bit more complex and Woelen's and I was going to write one for that formula mysqlf untill I found the author had already written one

 

Cheers' date='

 

Ryan Jones[/quote']

The funny thing of the code I have is that it uses an integer algorithm only and it is a globally convergent algorithm. If you analyse the program, then you see that it starts of with uninititalized data (meaning that any crap value can be in memory) and by applying the algorithm over and over again, it converges to pi.

 

This is not my own work. I found it many years ago (think 7 or 8 years or so) on a site, which was devoted to the so-called "Obvuscated C-contest". Well, this code is obvuscated and really hard to understand, but on the other hand, the principles behind it are really really nice and that's why I stored this snippet of code for all those years. Just compile it with any ANSI C compiler, ignore all warnings about uninitialized data and whatever more and run the executable.

 

I have a similar program for the computation of digits of the number e (2.71...).

[bascule]

Isn't there some weird kind of way to calculate pi using a fractional tutorial?

[RyanJ]

Isn't there some weird kind of way to calculate pi using a fractional tutorial?

 

Do you mean these: http://en.wikipedia.org/wiki/Pi#Continued_fractions

 

@ecoli: I was refering to a paper I read a while back that claimed a quantum computer could be made that could theoretically calculate an infinite number of calculations at once...not that it would do any good, no-one would live long enough to read the whole number even if it were possible.

 

@woelen: Its amazing some of the things you can find, always good to keep them because you never know when they may come in useful!

 

Cheers,

 

Ryan Jones

[bascule]

...using a fractional tutorial?

 

Gah, I meant a fractional factorial, and yes, it probably computes continued fractions...

[RyanJ]

Well, there is one like this:

 

[math]\sum^{\infty}_{n \; = \; 0} \; \left( \frac{n!}{(2n + 1)!!} \right)[/math]

 

Not shure if that was what you were looking for?

 

Cheers,

 

Ryan Jones

[Prime-Evil]

I would have guessed that compilers that have it as a function have it stored as a constant. But perhaps the best constant to use is machine specific, so maybe there is still a little computing, at least at compile time. Or as Big Bobby Clobber said, "I don't understand the question."

[woelen]

Compilers and systems, which use fixed precision numerical data formats (such as IEEE 754) use stored constants. Also processors, such as the Pentium have hardwired bit-patterns for PI.

 

There are, however, also software packages, which have user defined precision (e.g. computer algebra systems). These systems do not have stored values, but the values are computed as needed, but only once. The value is flagged as not available. When it is needed it is computed (which may take some time) and the flag is set. When the value is needed another time then its value is read again. As soon as the user changes the precision, then the flag of such constants is reset again, or the value is invalidated.

[Prime-Evil]

Good to know. Thanks.

I guess it does make sense that you can exceed the 'natural' numerical precision of any system through programming and so there will always be a need to come up with an algrithm to compute numbers such as pi to some arbitrary degree of precision. I can see it getting rather complicated, since you are still working within the 'natural' numerical precision of the system incuding any compilers you are using, and within other contraints such as memory and processing time and readability. The best algorithm would take these constraints into account also, but any algorithm is a good algorithm if you are confident that you can understand it and make it work, or even if it is just fun to think about.

[woelen]

There are many many good libraries, also as open source projects, which do the multi-precision math for you. Have a look at this:

 

http://www.swox.com/gmp

 

This is one of my favorite pieces of software and I have used it in quite some personal software projects, the most recent one being a generic polynomial equation solver for any type of roots and any required precision.

 

In fact, high-precision maths works in quite the same way as plain good old schoolboys arithmetic, where the computer's natural number size serves as a single 'digit' and where addition, multiplication, subtraction and division are done in the way, children learn this at school.

 

Only for VERY large numbers with thousands of digits, more advanced techniques are used for multiplication and division. One can resort to convolution or even FFT algorithms to perform multiplication in sub-quadratic time.

[RyanJ]

woelen: Do you happen to know if thats how Mathematical does it? It can solve stupidly large equations in a short period of time... I'm guessing they are custom written functions?

 

I would love to get my hands on the ource code for it

 

Cheers,

 

Ryan Jones

[5614]

If you tell a computer to sum something between x (whatever number you want x to be) and infinity then does the computer not crash because it is trying to sum to infinity? ie. do an infinite amount of calculations

[RyanJ]

If you tell a computer to sum something between x (whatever number you want x to be) and infinity then does the computer not crash because it is trying to sum to infinity? ie. do an infinite amount of calculations

 

Not really, if you have a specist package as woelen said it can split the sum up into parts, it can never be solved completly but it goes as far as it can. As long as your careful you can do just about anything

 

Cheers,

 

Ryan Jones

[woelen]

If you tell a computer to sum something between x (whatever number you want x to be) and infinity then does the computer not crash because it is trying to sum to infinity? ie. do an infinite amount of calculations

The computer does not crash, it goes on forever .

 

A nice example is this loop for solving the equation x = cos(x) numerically:

 

x = 0;
do
{
 x = cos(x);
}
while (true);

 

It never stops.

 

You need some stop criterion, e.g.

 

x = 0;
do
{
 double c = cos(x);
 eps = fabs(c - x);   // modulus of c - x
 x = c;
}
while (eps > 0.000001);

 

This example is an iterative procedure. For summation of series, the stop criterion usually is that an error estimate does not exceed a given value.

 

For alternating-sign convergent series, the error is less than the first term, skipped in the series. So, we can evaluate term by term, and when the term is smaller than the error threshold, then we stop. For same-sign convergent series, in general there is not a nice error-estimate. For each function, one has to to an analysis of the error as function of the index n, from where the series is truncated.

 

Another REALLY important quirk when evaluating series for estimations of functions is that the smallest term needs to be summed first. Many small numbers may add up to a larger number. But, when the larger numbers are evaluated first, then the summing of the smaller numbers may be lost, due to finite precision of the computer.

 

A somewhat exaggerated example, which clearly demonstrates what I mean:

We have a computer, which works with four digits of precision, in floating point format. So we can represent numbers like 0.0000001, as 1.000*10^7. But because of limited precision, a sum like 0.1 + 0.0000001 equals 0.1 on this computer (remember, it only can store 4 digits of precision and an exponent).

 

Now suppose we have a series with 1000 terms, each equal to 0.00001

There is one term, equal to 1.

 

If we start with 1.000 in the total, and we add the smaller terms to the total, then the final outcome will be 1, because 1.000 + 0.00001 = 1.000 (remember, only 4 digits are maintained).

 

Now, if we first add up the small terms, then we have 0.00001 + 0.00001 + .... (1000 times) = 0.01. Finally, we add 1.0 and the answer will be 1.010

 

You see? In computer science the following is not true in general: a+(b+c) = (a+b)+c. It only is approximately true.

 

Because of this effect, programming the summing of series in computers is harder than one would expect at first glance. If programmed carelessly, one can easily loose a few digits of precision and that would be sad.

 

A good software package determines all separate terms, stores them in an array of values, then sorts the values in increasing order of magnitude and then does the addition. Especially for large series this becomes very important!

[The Thing]

Many computers, especially older ones, still use Machin's formula or some form of arctan infinite series.

[ajb]

You can also use a Monte Carlo method for calculating pi, but is it rather slow. I once wrote a programe in BASIC to do it several years ago now. I do not suggest that it is a "good" method of calculation but it does work.

 

You can see how it work here

 

http://www.eveandersson.com/pi/monte-carlo-circle

[Neil9327]

If you just want to know what it is, to the nearest million decimal places, go to:

 

http://3.141592653589793238462643383279502884197169399375105820974944592.com/index1.html

 

The last 10 of the million are: 5779458151

 

(sorry did I spoil the ending for you?)

[Tom Mattson]

(because it's an infinately large number, you can't get an exact value)

 

Pi is less than 4, so it's definitely not infinitely large. The problem is not its magnitude, but rather the fact that it's irrational.