Jump to content

How is pi calculated on computers?


Nacelunk

Recommended Posts

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

Link to comment
Share on other sites

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...).

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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." :)

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

 

Cheers,

 

Ryan Jones

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 :D .

 

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!

Link to comment
Share on other sites

  • 5 weeks later...

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.