Why are large calculations so hard to compute?

Discussion in 'Computer Science & Culture' started by Xelios, Dec 20, 2001.

Thread Status:
Not open for further replies.
  1. Xelios We're setting you adrift idiot Registered Senior Member

    Messages:
    2,447
    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!
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. James R Just this guy, you know? Staff Member

    Messages:
    30,379
    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
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Xelios We're setting you adrift idiot Registered Senior Member

    Messages:
    2,447
    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?
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. James R Just this guy, you know? Staff Member

    Messages:
    30,379
    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.
     
  8. daktaklakpak God is irrelevant! Registered Senior Member

    Messages:
    710
    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.
     
  9. Porfiry Nomad Staff Member

    Messages:
    4,127
    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.
     
  10. (Q) Encephaloid Martini Valued Senior Member

    Messages:
    19,125
    pi

    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.

    Please Register or Log in to view the hidden image!

     
  11. James R Just this guy, you know? Staff Member

    Messages:
    30,379
    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.
     
  12. Porfiry Nomad Staff Member

    Messages:
    4,127
    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.
     
  13. Alpha «Visitor» Registered Senior Member

    Messages:
    1,179
    Pi is an infinite sequence of random numbers.
     
  14. James R Just this guy, you know? Staff Member

    Messages:
    30,379
    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.
     
  15. Porfiry Nomad Staff Member

    Messages:
    4,127
    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
     
  16. rde Eukaryotic specimen Registered Senior Member

    Messages:
    278
  17. scilosopher Registered Senior Member

    Messages:
    435
    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.
     
    Last edited: Jan 2, 2002
  18. Alpha «Visitor» Registered Senior Member

    Messages:
    1,179
    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.
     
  19. scilosopher Registered Senior Member

    Messages:
    435
    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.
     
  20. Xelios We're setting you adrift idiot Registered Senior Member

    Messages:
    2,447
    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.

    Please Register or Log in to view the hidden image!

     
  21. James R Just this guy, you know? Staff Member

    Messages:
    30,379
    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.
     
  22. Rick Valued Senior Member

    Messages:
    3,336
    I heard somewhere that quadrallionth digit of Pi is zero and after that it repeats itself??...??

    Please Register or Log in to view the hidden image!



    bye!
     
  23. Imahamster Registered Senior Member

    Messages:
    135
    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?
     
Thread Status:
Not open for further replies.

Share This Page