PDA

View Full Version : Why are large calculations so hard to compute?

Xelios
12-19-01, 06:45 PM
I don't know too much about computers, but I started to wonder one day why modern computers can't calculate something like the value of pi to as many decimal places as we want. Isn't the computer only doing one calculation at a time (the next step in the division process) and then storing the number it gets, moving on to the next one? I mean, if each number takes up one byte of information, and you had a 30 gigabyte HD you should be able to calculate pi to that high a precision too right?

My thinking must be flawed in here somewhere, because if it was this easy people would have done it already. If someone could point me in the right direction on this one it'd be great. Thanks!

James R
12-19-01, 09:38 PM
Computers <i>can</i> calculate pi to as many decimal places as you like. All you need is time. pi has been calculated to several billion decimal places already, though I can't see any conceivable application which needs more than about 40 places.

There's a fair amount of number crunching involved. Are you familiar with how pi is calculated? Usually it uses series expressions for pi. More terms of the series gives more decimal places. Alternatively, there are some very clever formulae which can calculate the nth digit of pi without calculating the previous (n-1) digits, but these tend to be more computationally intensive.

JR

Xelios
12-19-01, 11:13 PM
Ah. I was under the impression that you could calculate it as you would any other number. Say 5/3. You would divide 3 into 5 (answer being 1) then carry over the remaining 2 and divide 3 into that again and so on. Wouldn't it just move to the next number after it has stored the answer from the previous?

But still, if computers are able to run a couple hundred thousand calculations a second (or more?) why does it take so long to divide pi?

James R
12-20-01, 12:17 AM
Some people think that 22/7 is pi, but that's only correct to the first few decimal places. A more accurate fraction is 355/113, but it's still not pi.

22/7 = 3.142857 142857 142857 ....
355/113 = 3.14159292...
pi = 3.14159265358979232846....

All fractions have decimal expansions which repeat at some point, as you can see with 22/7 above. 355/113 also repeats, but only after 112 decimal places. But it is possible to prove that pi never repeats.

The upshot of this is that you can't calculate pi by dividing one number by another number, because you can't write pi as a fraction.

daktaklakpak
12-20-01, 04:00 PM
Originally posted by Xelios
But still, if computers are able to run a couple hundred thousand calculations a second (or more?) why does it take so long to divide pi?
It really depends how accure you want pi to be. If you just want a few millions digits, then it takes only a matter of seconds divide pi. And I won't call that is long.

Porfiry
12-20-01, 04:05 PM
Intuitively, from the perspective of information content, Pi contains an infinite amount of information. To compute its value totally would require either an infinite amount of memory (hopefully with the values already present) or an infinite amount of time.

An interesting consequence is that the sequence of Pi's digit contains all possible encodings of all possible information that ever could exist.

Similarly, a computer given infinite time can enumerate all possible encodings of all possible information that ever could exist.

This should be disturbing. Enjoy.

(Q)
12-20-01, 05:39 PM
Conceive a sphere constructed with the earth at it center, and imagine it surface to pass through Sirius, which is 8.8 light years distant from the earth... Then imagine this enormous sphere to be so packed with microbes that in every cubic millimeter millions and millions of these diminutive animalcula are present. Now conceive these microbes to be unpacked and so distributed singly along a straight line that every two microbes are as far distant from each other as Sirius is from us... Conceive the long line thus fixed by all the microbes at the diameter of a circle, and imagine its circumference to be calculated by multiplying it diameter by Pi to 100 decimal places. Then, in the case of a circle of this enormous magnatude even, the circumference so calculated would not vary from the real circumference by a millionth part of a millimeter.

This example will suffice to show that the calculation of Pi to 100 or 500 decimal places is wholly useless. :D

James R
12-20-01, 07:09 PM
Porfiry,

I don't think pi has infinite information content. Only a totally random infinite sequence of digits would have infinite information content.

The relevant question is: how much information do you need to completely specify the thing you're talking about? An algorithm for calculating pi can easily be given, so the information content of pi must be roughly equal to that of any algorithm used to specify it. On the other hand, a particular infinite string of random digits can only be specified by writing down all the digits explicitly, because no rule links one digit with the next. There's a pattern in pi, unlike a string of random digits.

Similarly, it is not necessarily true that pi contains all possible encodings of all possible information, since the information in pi is constrained to conform to a particular pattern, which is not necessarily true of all possible information.

Porfiry
12-20-01, 11:12 PM
An algorithm for calculating pi can easily be given, so the information content of pi must be roughly equal to that of any algorithm used to specify it. On the other hand, a particular infinite string of random digits can only be specified by writing down all the digits explicitly, because no rule links one digit with the next. There's a pattern in pi, unlike a string of random digits.

IIRC, there is no algorithm that can compute the n-th digit of pi without computing the n-1 preceding digits. So, while an algorithm exists, you require an unbounded amount of information to compute an arbitrary digit of pi.

Alpha
12-21-01, 03:30 PM
Originally posted by James R
I don't think pi has infinite information content. Only a totally random infinite sequence of digits would have infinite information content.Pi is an infinite sequence of random numbers.

James R
12-24-01, 12:01 AM
Porfiry,

There is at least one algorithm which allows the nth digit of pi to be calculated without knowing the (n-1)th digit.

alpha:

pi is not a sequence of random numbers. All the digits in pi follow a pattern: they're the digits of pi! They are always the same, no matter how many times you calculate pi, or what method you use to do the calculation.

Porfiry
12-24-01, 01:08 AM
Interesting, James. If you have a reference to this algorithm, I'd appreciate it. Obviously if this is true, then what I've been saying is indeed incorrect.

Thanks

rde
12-24-01, 01:14 AM
Algorithm for finding nth digit of pi can be found at http://www.mathsoft.com/asolve/plouffe/plouffe.html .

scilosopher
01-02-02, 01:19 PM
If you had a long enough string of random digits most of the time you could probably find patterns in it anyway. There are lots of different possible patterns, so even a totally random string of digits is likely to have some redundancy. At least that's what I'd think intuitively (it would just take a lot of computation time and most compression algorithms focus on text because that's the most wasteful).

I wouldn't consider the digits of pi random either, but if you chopped of the first 100 digits and gave the string to someone I bet they would never guess it was pi [or rather part of it ...]. I think random is relative to your amount of knowledge (Try to imagine a physical mechanism that's random). That's why random strings and strings with high information content are essentially indistinguishable.

Alpha
01-02-02, 02:43 PM
Originally posted by James R
alpha:

pi is not a sequence of random numbers. All the digits in pi follow a pattern: they're the digits of pi! They are always the same, no matter how many times you calculate pi, or what method you use to do the calculation.Just because the sequence is always the same doesn't mean it's not random. You can make a random sequence of numbers, and use it in as many instances as you like and it's still a random number.

scilosopher
01-02-02, 05:15 PM
Alpha, what is your definition of random?

Even if the sequence internally has no obvious pattern, I would say it's relationship to the radius and circumference of a circle qualify it as giving the sequence an ordered pattern.

Xelios
01-17-02, 12:10 AM
Is there a repeating pattern after so many decimals in pi? Ie. ...24242424 or something like that? Or is it a whole swack of different numbers? I just don't see how any value can be a chain of infinite numbers, if there is no pattern in them at all. :confused:

James R
01-17-02, 07:37 PM
Xelios,

pi cannot have an endlessly repeating pattern like 242424 after any number of prior decimal places. If it did, it could be written as a fraction, and would be a <i>rational</i> number. But it has been proven that pi is irrational.

Rick
01-18-02, 06:24 AM
I heard somewhere that quadrallionth digit of Pi is zero and after that it repeats itself??...??:confused:

bye!

Imahamster
01-18-02, 12:40 PM
Zion, possibly the entity was stating a useful engineering approximation similar to using 3.14 at the “value” for Pi. Perhaps the entity meant that the quadrallionth digit of Pi is zero and the next sequence of a quadrallion quadrallion digits of Pi happen to be zero. After that the entity didn’t care…being an engineer and not a mathematician. Hehe.

Is Pi erotic…err…that is, ergodic?

James R
01-18-02, 10:06 PM
zion,

Your source was wrong.

Rick
01-19-02, 06:23 AM
Its quite possible that my source could have been wrong...

bye!

Bagman
01-21-02, 05:01 AM
Xelios,

Pi is not the quotient of two integers; it's not 22/7 or any other quotient of integers. A number that is not the quotient of integers is called an irrational number. So pi is irrational. But a number that is irrational and is not the root of any algebraic equation is called transcendental. Pi is transcendental.

There's a simple proof, due to the Greeks - Euclid, I think - that the square root of 2 is irrational. You might want to look that up.

aerosimon
01-28-02, 08:38 AM
you said that pi is a number which does not contain recurring decimals and that it is infinite, i've heard that the number pi is infinite from some other people as well as you but i was thinking that since they havent calculated the exact value of pi, how do they know its infinite and dont have recurring digits at the end? who knows, imagine one day we'll find a fraction that number lol

btw, is the number pi calculated by circumference/diameter or circumference/radius? i forgot :confused:

Imahamster
01-28-02, 01:27 PM
Aerosimon, take a number X = 0.55…. multiply it by 10 to get 10 X = 5.55… Now subtract X from 10 X to get 9 X = 5.0 Divide both sides by 9 to get X = 5/9 = 0.55…

A very similar process allows one to convert any repeating series of decimals to a ratio of integers. Proving pi is irrational is a little harder.

As for your second question… Picture a circle with diameter 1. Now imagine the diameter is a made of rubber and pull the center point of the diameter to the edge of the circle. Consider how much the diameter has to stretch. Not even close to three times right? Closer to 1.5 times. Now stretch a few more points from the “diameter” line to touch the circumference. Not much longer and now it’s following along half the circumference. (Opps...let's get it right this time. Hehe.) So half the circumference is close to 1.5 times the diameter. The circumference equals pi times the diameter. If you imagined all this you should have a way of remembering this formula. You’ll also have a good idea of how the Greeks calculated the value of pi.

James R
01-28-02, 07:44 PM
aerosimon,

It can be proved that pi is an irrational number (i.e. that it cannot be written as a fraction). The proof requires some complicated mathematics, which I can't teach you in this thread. But all mathematicians accept that the proof is valid.

This means we don't need to calculate pi to know it is irrational.

aerosimon
01-28-02, 11:54 PM
ok thanks for the info Imahamster and James R. lol James, even if you did show me the mathematics involved to prove that pi is irrational i dont think i'd understand it :o . maybe one day but definetely not now :D

Rick
01-29-02, 03:45 AM
Excuse me...is this Computer Science forum?

erm...may be i tumbled on to a wrong place.as i told Porf,that we need a Math forum to satisfy our mathematical itches,i am sure untill then people will continue to Bash computer science forums for that purpose... ;)

;):D

bye!

James R
01-29-02, 06:35 AM
You'd be surprised at how much computer <b>science</b> is tied up with maths, one way or another.

Rick
01-30-02, 08:28 AM
DEJA VU...

As i pointed out earlier,any Science is incomplete without Maths...
:D ;)

bye!