Calculating Pi

[benthehutt]

So I was thinking the other day about the number Pi (3.1415926535.....) and how it is calculated on computers nowadays to the ten kabajillionth place and I started to think, "hey!  I'll write a program and have it run on an old P1 I have laying around for a couple years."

But then I realized, I have no idea how.  I'm not asking how to write one, but how the crap do programs that calculate pi store it?  Even the biggest number classes in C++ (I use that as an example because I know it--kinda) can only store to the thirteenth or so place!  How the crap can you calculate a number with fifty million digits after the decimal?

I suppose no one will respond to this, that's okay, I'm just butt-confused...

[Metgod]

I'll respond...

"Good question!"


Actually the only thing I can think of (and that doesn't mean fact) is using pointers and malloc (or for C++ then new)... or several variables and combining them some how.

But if you use pointers you can create as much space as your system can handle... creating an array of sorts...


When I use bitvectors I sometimes wish double would hold more bits than a long... but it still overflows passed (1 << 30) ... that is, (1 << 31) would return negative because it's too large...

Very frustrating... so the solution to that is to use another variable (which is probably what made me think of my thought for this question of yours).

[godaigo]

I suppose you could try to define your own variable type although I'm not really sure what the limits are on that. All I know is that it is possible with C++. I'll do a bit more research and see what I come up with, because maybe I'm on crack and I'm just imagining things!

[Metgod]

well.. you can't in C.. alas

Well.. at least not larger ranges for numbers.

I suppose some might call 'typedef' and 'enum' and such your own types but not by my book anyway (because it's still limited to the types in the language).

But would be neat if it were possible some how... only other thing I can think of is special extensions to the language (libraries or so) ....

Interesting question though..

[benthehutt]

Is there really no limit as to how big your variable types can be?  I mean, it seems to me that if the var got bigger than 8 bytes, you'd have to program something differently because a normal 32-bit processor has an internal bus width of only 64 bits (8 bytes), so the processor can only manipulate data in 64 bit chunks...

Of course, that may have no bearing on the situation...

But even if it doesn't, to create a variable that can hold something with 50 million digits seems well beyond what any computer can do now.  Just storing the number in notepad takes 50 MB.

Creating a 40 bit var would only get you 319 digits.  Imagine getting to the current record of 50,000,000,000 (50 bil)!

[godaigo]

I guess you could just continually dump it to an output buffer and have it print, well as long as your printer could keep up and the paper didn't run out!   Anyway, I finally got my computer at home up an running so I'll do some C++ checking. But ben I think you're right there's got to be a limit on how far you could set your variable length. (Although as the early years of hacking show us, and heck even today, these things get overlooked). Cheers....

[benthehutt]

Thanks godaigo, you know 'erthang.

[Metgod]

I don't know why I didn't think of this before... but in Linux/Unix (and maybe other os's as well) the long long int is 64 bits...

Code: [Select]

/* Maximum value an `unsigned long long int' can hold.  (Minimum is 0.)  */
#   define ULLONG_MAX   18446744073709551615ULL

taken from limits.h

Of course the solution to my problem with overflows in (1 << 31) or higher is also right there. Because 'long long' is 64 bits, so it's possible to make up to (1 << 62) if you specify ULL.

I still don't know the way calculators store higher than that, but I imagine it's some extension or some clever hack.

As for the printer deal, I would think unless you have a certain calculation, it'd be potentially problematic, because you can't append the numbers since how could you calculate the next one if it's too big ?

I.e., 1.0000111111111 ... you can only go so far, and then you get inaccurate results, so how can you figure out what will be the next digit is, if you don't even know what the current is ?

(that or my ignorance about pi is more than I realize :))

[godaigo]

Metty, I'm glad that you replied, I kinda spaced out about this (alot going on at work). It's really an interesting question. I presume that there is a solution considering that many different institutions around the country are continually calculating the values of pi. I would think that a person could probably run google scholar (does everyone know about that?) search and find out who's doing research on that. Many academics would be happy to share code with interested people. I think that probably there's gotta be some code that addresses these issue's floating around on the internet as well. If I get a chance I'll look into this.... sorry for not following up ben.....

[godaigo]

Actually there is an open source project for this. I just put into google "calculating pi" and came back with a ton of stuff. Here's the URL: http://sourceforge.net/projects/projectpi/

And here's a distributed project: http://www.cecm.sfu.ca/projects/pihex/

Hope that helps!

[Metgod]

google scholar... hrm... I have a guess what that is but I actually don't know for sure.

But truthfully, I'm a lot more interested in pie.

[benthehutt]

I know you're probably not actually interested in pi anymore (or ever before), but I'm a math major so I have to explain how pi is found to such amazing decimal places.  Here is one way known as Leibniz's infinite summation:

PI       1         1          1
-- = ----- + ----- + ------ + ...
8     1 x 3    5 x 7    9 x 11

You get to PI when you have an infinite amount of terms.  Seems strange, but yes, when you add an infinite amount of finite numbers, you can get PI/8.

So if I were writing a program, I would start with one term and gradually add more to get a more exact answer.

...i know i need to get a life, shut up...

[Metgod]

What can I say.. pie sounds a lot nicer than pi.

Seriously though, I don't do well with math (unfortunately) and I'm too lazy (or I'm too absorbed in the things I do to actually learn more -- that's my problem these days). To give you an idea, I didn't even follow what you said.

So I do like to learn more (okay, love), but it depends on what. More coding stuff.. protocol.. networking.. security I'm all for, but for some reason I stay away from math.  But pi is an interesting number... I don't know why it's necessary to go so far with it though, because after a certain point, it's kind of useless (my opinion), but it's still interesting.

In my highschool days, someone was in a math class (period before mine) that memorized pi to quite some digits. How I'd love to have that kind of memory...

Maybe my problem is that I don't see the use for it. They say you use math in every day life, but honestly, I've not met one person other than a math major, who uses math in every day life. That includes engineers that don't need it.

Two things in math I do enjoy though.. binary and hexadecimal

and I'm just blabbering so I'll end this...

[godaigo]

Yeah, but it was on-topic and interesting blather!   I really like math, but I didn't when I was younger so I'm having to go back and relearn a lot. I'm working on calc, but have a lot of interest in algorithm analysis and matrix theory (for all those cool 3D types of things) Add that to an interest in information theory and I really need to buckle down on my math! I admire your courage for actually doing it as a major though ben!

[benthehutt]

Aw, shucks...

Anyway, as to Metty not understanding the use for the billionth digit of pi, here's something to think about:

There is not use.

I just think it's cool how a stupid ratio between circumference and radius can have an infinite amount of repeating digits.  I think that's why people keep calculating stupid exact approximations--cause they want to see if any non-randomness does occur.

Anyway, enough blab.

Go calculus and riemann geometry!!