calculating the value of pi

[bryan.6]

more for topic of discussion than my implimentation...
what would be the most efficient way to calculate pi?

the one way i know of is pi = 4( 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 ... )
(due to Leibniz)
i implemented this in perl (obviously if seriously doing this perl would not be the best language), and it works, but it is VERY slow... ran for probably 10 minutes before it finally found accuracy to the 4th digit, and as it goes on it will take longer and longer to find each digit.

any other (time efficient) ways of which you know?

[mage492]

No other way springs to mind... I've got another question, though.

How do you get around the problem of floating-point precision? As the program runs, it'll be calculating smaller and smaller fractions. Wouldn't this eventually start to become more and more inaccurate?

[knute]

That would be 22/7. :D

[OmarSerenity]

pi/4=4*arctan(1/5)-arctan(1/239)

is the only other one I know.

[OmarSerenity]

Here's another. Don't know how it'll look without all the fancy mathematical characters:
/ \
| |
| n*sin(360/n) |
pi = lim | _______________ |
n -> infinity | |
| 2 |
| |
\ /

[SL1200MK4]

With the floating point precision problem, you basically have to design your own data structure to store extreme high precision floting point numbers or extremely large integers. Even with 128bit you will be rather limited.

For example, one can store the result in characters. Which makes displaying of the result a lot easier. However, this always means that one has to convert the result of the mathmatical operation to characters. Then in such case, one is limited by the size of the storage device.

[bryan.6]

i know in perl, and i think in java, there is something called BigFloat (and BigInt, but that's not what we are looking at). Wouldn't that work? Does that have enough precision? Supposedly it's for a float with an infinite amount of decimal places.

[bryan.6]

Originally posted by OmarSerenity
Here's another. Don't know how it'll look without all the fancy mathematical characters:
/ \
| |
| n*sin(360/n) |
pi = lim | _______________ |
n -> infinity | |
| 2 |
| |
\ /



hmm... i think in the computer sine is an approximation too, so you'd have to use something to evaluate sine to it's exact value.

[sploo22]

According to this page (http://www.cacr.caltech.edu/~roy/upi/pi.formulas.html), some of the fastest approximations use the expansion:

arctan x = x - x**3/3 + x**5/5 - x**7/7 - ...

Then pi can be found using something like the formula pi/4 = 4*arctan 1/5 - arctan 1/239.

They leave implementation as an exercise for the reader, of course... :D

As for the precision problem, there's a library called GMP for C/C++ that handles arbitrary-precision numbers. I don't know anything about Perl, but I would assume that somebody, somewhere has ported it or a similar library.

[sharth]

Originally posted by bryan.6
more for topic of discussion than my implimentation...
what would be the most efficient way to calculate pi?

the one way i know of is pi = 4( 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 ... )
(due to Leibniz)
i implemented this in perl (obviously if seriously doing this perl would not be the best language), and it works, but it is VERY slow... ran for probably 10 minutes before it finally found accuracy to the 4th digit, and as it goes on it will take longer and longer to find each digit.

any other (time efficient) ways of which you know? I should have done this in c++ about a week ago (halfway done).

It runs fairly quick there...

[mage492]

Originally posted by sploo22
As for the precision problem, there's a library called GMP for C/C++ that handles arbitrary-precision numbers.

I'm reading about it, now, and it looks awesome! I'll have to try it out, later...

[OmarSerenity]

Originally posted by bryan.6
hmm... i think in the computer sine is an approximation too, so you'd have to use something to evaluate sine to it's exact value.

Yeah, I was thinking about that, too, after I posted. I was thinking that computers probably use an approximation of pi to calculate sine anyway. Both of my examples use trigonometric functions, so they would be of little help.

I'm relatively new to computers, so I don't really understand the 'floating point precision problem' y'all are referring to either.

[Strogian]

If you want an exact answer (i.e. so you can say "1/3 - 1/5 + 1/7 + ... 1/n" is EXACTLY a/b, and THEN approximate it as a decimal if you want to), you might want to write the program to do fractional additions with integer numerators and denominators. (Still use GMP for arbitrary precision, but use integers rather than floats) I'm not sure which way would be quicker, though. One way does a float division and addition for every cycle, and the other would do, I guess, 3 integer multiplications and an addition.

I just feel like it's a waste to have to start from scratch every time you run the program, especially if you just want to add some more decimal places.

Hmm.. am I making sense? :D

[mage492]

Originally posted by OmarSerenity
I'm relatively new to computers, so I don't really understand the 'floating point precision problem' y'all are referring to either.

Basically, here's the problem. Okay, in a computer any number is expressed in binary, a system based on powers of 2. So:
17 = 10001 in binary

That's pretty easy. Now, for non-integers, it gets a bit tougher. Here's how the values of binary digits go.

16, 8, 4, 2, 1, (the decimal), .5, .25, .125, etc...

Now, there are some numbers (.123 is one, I believe) that can't be represented with complete accuracy, in binary. Using negative powers of 2, you can't express that number. However, the more binary digits you set aside for it, the better the approximation.

When you start dealing with infinite series of smaller and smaller fractions (or trig functions), little inaccuracies add up over time.

I'm not sure how much of that you knew, before hand, but I tried to err on the over-informative side.

[dboyer]

Originally posted by sharth
I should have done this in c++ about a week ago (halfway done).

It runs fairly quick there...

my c++ implementation can calculate it out to 4 digits nearly instantly, and about... 79,000 iterations... the code can probably be optomized a little further, but there isn't much point...

[bwkaz]

Originally posted by mage492
Now, there are some numbers (.123 is one, I believe) that can't be represented with complete accuracy, in binary. 0.1 is definitely one. :)

[OmarSerenity]

Originally posted by mage492
<<snip>>

I'm not sure how much of that you knew, before hand, but I tried to err on the over-informative side.

Well, I never really stopped to think about the problem representing irrational numbers in binary, but now it makes perfect sense. I much prefer someone to err on the side of over-informative. Thanks.

[bryan.6]

yeah, i came to realize that printing to the screen was really what was causing the slowdown, not all of the calculation, but still, thousands of iterations.
i implimented the atan( 1/5 ) - ata.... version, that works INSANELY faster! like, 5 or 6 iterations gives 4 digits of precision. still trying to work out the "BigFloat" deal, i don't really understand it all, and i'm still getting just around 10 digits or so.

[mage492]

Originally posted by OmarSerenity
Well, I never really stopped to think about the problem representing irrational numbers in binary, but now it makes perfect sense. I much prefer someone to err on the side of over-informative. Thanks.

No problem! It kinda confused me when I first heard it, too.

[bryan.6]

i didn't really realize that was the problem. i just thought it had to deal with if you are trying to calculate pi, you want as many decimals as possible, and the largest data type only holds like 32 places. guess i was wrong. I believe BigFloat solves the problem by holding the number as a whole number with a 10^x exponent.

[o0zi]

Why calculate when you know it to several places from memory? :)

3.141592635358979323846264338327950288419716939937

(yes, that was from memory)

[bryan.6]

wow, i'm really impressed (I've got 3.14159, and that's all). i really see no point to memorizing that, but hey, that's cool, i'm sure you pick up all the chicks with that one, huh?

[OmarSerenity]

I have it memorized as 3.1415927 and that's about as far as we needed to know it.

[bae127]

Pi = 4.0 * atan(1.0)

This calculates Pi to the declared precision for Pi in Fortran...

If other languages can calculate the inverse tan function to machine precision - I don't see why this wouldn't work for other languages...

[sharth]

Originally posted by bae127
Pi = 4.0 * atan(1.0)

This calculates Pi to the declared precision for Pi in Fortran...

If other languages can calculate the inverse tan function to machine precision - I don't see why this wouldn't work for other languages... neato :) works in gnumeric too! :p

[bryan.6]

is FORTRAN the mathematics language, or was that PASCAL. if i'm right, one of them is business and one is math, right? at least at the start i mean. or am i way off base?

[Trogdor]

Originally posted by OmarSerenity
Here's another. Don't know how it'll look without all the fancy mathematical characters:
/ \
| |
| n*sin(360/n) |
pi = lim | _______________ |
n -> infinity | |
| 2 |
| |
\ /


I'm no math prof, but that looks like the definition of pi, not a (efficient) way of solving it.

[drummerboy195]

we are working on sums of sequences in clac right now, and if it wasnt for the pesky change in signs every other number, it could be expressed as the sum of 4(1/(2i-1)) as i goes from 1 to infinity. except, the real sum should be 4(1/(2i-1)-1/(2i/1)+1/(2i-1)-1/(2i/1)+1/(2i-1)........) anybody know how to set that up?

[bryan.6]

yeah, that's the one i mentioned right away, it's quite slow. anyway, the way i set it up was something like this...
my $pi = 0;
my $x = 0;
my $sign = 1;

while( 1 ) {
$pi= $sign / $x;
$sign = -$sign;
$x+=2;
}

[Strogian]

(-1)^n
cos(pi * n)
-1 if n is odd, 1 if n is even

they all work. :)

[Strogian]

One question I have though.. How is the computer calculating the trig functions? I like the sum one because I know what it is doing. :)

[bwkaz]

The x86 math coprocessors (x87 if x <= 3) have instructions that can be used to calculate trig functions.

I don't know how accurate (or precise) they are, though... probably only to the machine floating-point precision (either 32 or 64 bits, or 80 if your compiler supports "long double").

[bryan.6]

with the atan suggestions, the taylor series expansion is used...
atan(x) = x - x^3/3 + x^5/5 - x^7/7 ...
or
atan(x) = summation from n=1 to infinity of (-1)^(n+1)*x^(2n-1) / (2n-1)
so each iteration you just add another term and it gets closer to the exact value of atan(x), which can be used to find pi in a number of ways.

[o0zi]

Are you sure the computer uses Taylor series? They're very slow; I think x86s have some binary method which involves mathematical rotations.

[bryan.6]

sorry, misunderstanding. no, i highly doubt that the computer uses the taylor series. i'm saying the programmer could use that method to get perfect accuracy for atan, instead of using the machine's approximation of atan.

[grady]

This page shows many unusual representationsmathworld (http://mathworld.wolfram.com/PiFormulas.html).

[Trogdor]

Originally posted by o0zi
Why calculate when you know it to several places from memory? :)

3.141592635358979323846264338327950288419716939937

(yes, that was from memory)

Damn! That is three digits more than I have memorized!

[questionasker]

just use the pi button on a calculator.

ha ha.

[knute]

Why?

Why do you need to calculate pi down so far?

Are you perchance shooting a rocket across the galaxy and need to hit a target on Vega the size of a grapefruit or what?
:cool: (That'd be really cool if you were though):cool: :D ;)

[o0zi]

You might as well ask the same of most of mathematics - it's an intellectual pursuit which many people enjoy merely for the fun of it, and not the practical value.

[Ath0s]

Originally posted by o0zi
Why calculate when you know it to several places from memory? :)

3.141592635358979323846264338327950288419716939937

(yes, that was from memory)

Don't know if this was a typo or not, but a published value is:

3.141592653589793238462643383279502884197169399375 11

(you've got an extra 3 in the 8th digit to the right of the decimal point).

;)

[o0zi]

Yup, sorry, typo :(

3.141592653589793238462643383279502884197169399375 10582

[Strogian]

You just put that there to make us think you took it from memory.

Impostor. :eek:

[Pafnoutios]

Originally posted by drummerboy195
we are working on sums of sequences in clac right now, and if it wasnt for the pesky change in signs every other number, it could be expressed as the sum of 4(1/(2i-1)) as i goes from 1 to infinity. except, the real sum should be 4(1/(2i-1)-1/(2i/1)+1/(2i-1)-1/(2i/1)+1/(2i-1)........) anybody know how to set that up?

4*sum((-1)^(i+1)/(2*i-1),i,1,infinity)=4(1-1/3+1/5-1/7...)

[andysimmons]

Originally posted by knute
Why?
That's how nerds entertain themselves.

Andrew Wiles (http://en2.wikipedia.org/wiki/Andrew_Wiles) locked himself up in an attic for 7 years working up a proof to Fermat's Last Theorem. Nobody knows what to do with it now, but at least Wiles had fun. :)

[sasKuatch]

As for precision, writing in Lisp might solve your problem. It has arbitrary precision.

For example, 123 to the 512th power is

10750212695898569850229900795908756510657751092214 25766372684899534590912545803820970882403606124803 29623988239057649301964005819628667410149974047158 95376388010430826493035570640067803753487438708113 21792489762756192239192227385412244576338384748428 72377563699897136638080094320246534628215703451104 49359665327161271738180860646924591803760295046336 08677240476576498563612501274856951516338922504567 50896615403255957644696741521612269841493610028679 43515430674550382553495430546391276630441063732563 66958673233879775770718866313465226951244429032639 93166043796665069900863003407954115005768041619522 10404852423618525763199254323952752609418490783383 36619080700032306715558586315388757199142551817743 79360045203846915295242881829870333614969876156978 48313289506911988333844214264536804521311956310670 69486001860323239861630769754407714069398461756033 51863162704712370347362560007777581334128585904030 16230055216225576139985834044790160665129334880786 38549024464944601082084119623880754010488900013211 04837575142081956433133495681209310396264804523268 484100203125583902721

... according to lisp, and it did that rather quickly. Can somebody check me on that please?

... so I'm sure it would have no problem calculating pi out to something longer than a calculator can do.