Slashdot stories can be listened to in audio form via an RSS feed, as read by our own robotic overlord.

 



Forgot your password?
typodupeerror
Math

New Pi Computation Record Using a Desktop PC 204

Posted by kdawson
from the more-digits-than-you dept.
hint3 writes "Fabrice Bellard has calculated Pi to about 2.7 trillion decimal digits, besting the previous record by over 120 billion digits. While the improvement may seem small, it is an outstanding achievement because only a single desktop PC, costing less than $3,000, was used — instead of a multi-million dollar supercomputer as in the previous records."
This discussion has been archived. No new comments can be posted.

New Pi Computation Record Using a Desktop PC

Comments Filter:
  • Verification (Score:3, Interesting)

    by Tukz (664339) on Tuesday January 05, 2010 @02:38AM (#30652224) Journal

    I didn't read the article, only the summery but it made me wonder.

    Do they verify these numbers somehow?
    Anyone can write down a series of a numbers and claim it's a specific sequence.

    Not saying these numbers aren't correct, just a thought.

    • One thing to say (Score:5, Informative)

      by DirtyCanuck (1529753) on Tuesday January 05, 2010 @02:42AM (#30652250)

      From the FAQ

      "How does your record compares to the previous one ?
      The previous Pi computation record of about 2577 billion decimal digits was published by Daisuke Takahashi on August 17th 2009. The main computation lasted 29 hours and used 640 nodes of a T2K Open Supercomputer (Appro Xtreme-X3 Server). Each node contains 4 Opteron Quad Core CPUs at 2.3 GHz, giving a peak processing power of 94.2 Tflops (trillion floating point operations per second).

      My computation used a single Core i7 Quad Core CPU at 2.93 GHz giving a peak processing power of 46.9 Gflops. So the supercomputer is about 2000 times faster than my computer. However, my computation lasted 116 days, which is 96 times slower than the supercomputer for about the same number of digits. So my computation is roughly 20 times more efficient. It can be explained by the following facts:

              * The Pi computation is I/O bound, so it needs very high communication speed between the nodes on a parallel supercomputer. So the full power of the supercomputer cannot really be used.
              * The algorithm I used (Chudnovsky series evaluated using the binary splitting algorithm) is asymptotically slower than the Arithmetic-Geometric Mean algorithm used by Daisuke Takahashi, but it makes a more efficient use of the various CPU caches, so in practice it can be faster. Moreover, some mathematical tricks were used to speed up the binary splitting. " ( http://bellard.org/pi/pi2700e9/faq.html [bellard.org] )

      Mathematical and Programming Ownage.

      • by Anonymous Coward on Tuesday January 05, 2010 @03:19AM (#30652436)

        HE USED TRICKS!!!!1111Burn the witch...eehh communist...eeeh climate researcher...eeeeh....PI guy.


      • The Pi computation is I/O bound, so it needs very high communication speed between the nodes on a parallel supercomputer. So the full power of the supercomputer cannot really be used.

        The algorithm I used (Chudnovsky series evaluated using the binary splitting algorithm) is asymptotically slower than the Arithmetic-Geometric Mean algorithm used by Daisuke Takahashi, but it makes a more efficient use of the various CPU caches, so in practice it can be faster.

        Before the next Top 500 list is published in June,

        • by onepoint (301486)

          I would love to give you mod points as insightful.

          The first thing I thought of after reading was .... How to run this as a 10 minute test on a personal computer as a benchmark I/O.

          I looked at the FAQ and it seemed that ram was not the real issue but the I/O is the most important part. so again, this might be the best tool for testing systems for I/O performance ...

          I would think that it might be interesting to test this on raid systems, database servers and anything that has a ton of read/writes and since it

      • Re:One thing to say (Score:5, Interesting)

        by PinkyGigglebrain (730753) on Tuesday January 05, 2010 @03:24AM (#30652468)
        An answer is a reply but a reply is not always an answer.
        • If you reply to the first post, it's almost just as good as having the 1st post. You get more views. So then the next guy replies to that reply, so on and so forth. Mods be on the lookout for offtopic.

      • by digitalhermit (113459) on Tuesday January 05, 2010 @04:04AM (#30652682) Homepage

        In another thread someone had posted that there was no reason for any modern CPUs; the idea being that anything one could reasonably want to do with a computer was possible with decade old hardware.

        This.. *This* article is why I enjoy the breakneck pace of processor speed improvements. The thought of being able to do some pretty serious computing on a relatively inexpensive bit of hardware -- even if it takes half a year to get results -- does what the printing press did. It allows the unwashed masses (of which I am one) a chance to do things that were once only the realm of researchers in academia or the corporate world. Sure, all that you need to do some serious mathematics is a pen and paper, but more and more discoveries occur using methods that can only be performed with a computer.

        There's always the argument that cheap computers and cheap access to powerful software pollutes the space with hacks and dilletantes. People have said this about desktop publishing, ray tracing, and even the growth of Linux. But it's this ability to do some amazing things with computers that makes it all worthwhile.

        • It allows the unwashed masses (of which I am one) a chance to do things that were once only the realm of researchers in academia or the corporate world

          I agree, that's why I have great hopes for my atomic bomb.

        • by ceoyoyo (59147)

          Give that someone a decade old processor and see how happy he is.

    • Re:Verification (Score:4, Informative)

      by msclrhd (1211086) on Tuesday January 05, 2010 @03:15AM (#30652412)

      In TFA (especially the PDF), the verification method is to use another algorithm to check the output. The PDF on Fabrice's home page goes into more details.

      NOTE: The machine they were using to generate the second result broke, so they used another (3rd) algorithm to generate the last digits.

    • Re:Verification (Score:5, Interesting)

      by David Jao (2759) <djao@dominia.org> on Tuesday January 05, 2010 @03:20AM (#30652444) Homepage

      I didn't read the article, only the summery but it made me wonder.

      Do they verify these numbers somehow? Anyone can write down a series of a numbers and claim it's a specific sequence.

      Not saying these numbers aren't correct, just a thought.

      Perhaps this is why you should read the article. The press release [bellard.org] answers this question directly.

      The binary result was verified with a formula found by the author with the Bailey-Borwein-Plouffe algorithm which directly gives the n'th hexadecimal digits of Pi. With this algorithm, the last 50 hexadecimal digits of the binary result were checked. A checksum modulo a 64 bit prime number done in the last multiplication of the Chudnovsky formula evaluation ensured a negligible probability of error.

      The conversion from binary to base 10 was verified with a checksum modulo a 64 bit prime number.

      • Fascinating about the Bailey-Borwein-Plouffe formula [wikipedia.org] for quickly generating an arbitrary digit of pi. Reading the FAQ, he doesn't offer the entire series of PI, but does offer excerpts. The devil's advocate in me can't help but point out that he could have prepared these excerpts using the above formula, rather than actually calculating pi to that many places. I suppose even if he did offer the entire result, nobody could verify it except by generating it himself.
    • by Xest (935314)

      You don't need to verify that the number is correctly pi to the given digits, merely verify that the algorithm calculates the digits of pi correctly.

      The algorithm can be proven correct in a number of relatively quick and easy ways.

      The algorithm is really also arguably the most important part anyway rather than the digits themselves because it's the part of most use.

    • From the PDF on his website:

      A standard desktop PC was used, using a Core i7 CPU at 2.93 GHz. This CPU
      contains 4 physical cores.
      We put only 6 GiB of RAM to reduce the cost. It means the amount of RAM
      is about 170 times smaller than the size of the final result, so the I/O performance
      of the mass storage is critical. Unfortunately, the RAM had no ECC (Error
      Correcting Code), so random bit errors could not be corrected nor detected. Since
      the computation lasted more than 100 days, such errors were likely [12]. Hopefully,
      the computations included verification steps which could detect such errors.
      For the mass storage, five 1.5 TB hard disks were used. The aggregated peak
      I/O speed is about 500 MB/s.

      A weird choice of words...

    • Re: (Score:3, Interesting)

      Verification as actually quite easy, due to the (totally unexpected at the time!) discovery of the Borwein-Bailey-Plouffe [wikipedia.org] algorithm which allows you to directly calculate the N'th hexadecimal digit of pi, without having to determine any other digits.

      He used this on a bunch of the last digits and they all came out correct, which makes the probability of an error extremely small.

      Last year I used his algorithm to calculate 1e9 (i.e. a US billion) digits of pi and made them searchable:

      http://tmsw.no/pi-search/ [tmsw.no]

      T

  • But will it help us in getting flying cars?
  • Finally! (Score:5, Funny)

    by pEBDr (1363199) on Tuesday January 05, 2010 @02:45AM (#30652266)
    Now I can finally get somewhat reasonable precision when calculating the radius of stuff!
    • It's still waaaaaaaay off.

      Can't get precision anymore these days, everything's just rush-rush, nobody takes the time to do it right...

    • Forget the radius. Now I can calculate zero to 2.7 trillion digits of precision: pow(e,i*pi)+1=0
    • Re: (Score:3, Insightful)

      by HTH NE1 (675604)

      I think you'll find you don't need anywhere near that level of precision of pi to find the radius of the Universe in Planck lengths. 50 digits is sufficient.

  • They figured this out... they post some, not all of the data, and therefore survive the slashdotting.
  • by Trepidity (597) <delirium-slashdot AT hackish DOT org> on Tuesday January 05, 2010 @02:47AM (#30652280)

    For those not previously familiar with Fabrice Bellard, he's known for:

    • LZEXE [bellard.org], very popular in the early 1990s as the first EXE-shrinker for DOS, or at least the first widely available one
    • ffmpeg [ffmpeg.org], video decoding library which he started and headed for a number of years
    • QEMU [nongnu.org], dynamic-translating generic emulator
  • by c0mpliant (1516433) on Tuesday January 05, 2010 @02:52AM (#30652302)
    Core i7 clocking at 2.93GHz 6GB RAM 5 1.5TB Hard Drives (At least 7.2TB needed to store final result and base conversion)

    He will be releasing the program he created for Windows (64bit only) and Linux
  • by LostCluster (625375) * on Tuesday January 05, 2010 @02:54AM (#30652320)
    1 TB data files... somebody needs to help him with the compression! Oh, wait a minute.
    • Wait, I have it right here! [wordpress.com] (could have gotten it inline, but slashdot doesn't do unicode, sorry).
    • by russotto (537200)

      1 TB data files... somebody needs to help him with the compression!

      Here's a full-precision compressed representation of Pi. The trick, of course, is expanding it:

      pi = 4 * sum(k,0,+inf, ((-1)^k)/(2k+1)))

  • silly (Score:2, Flamebait)

    by dsanfte (443781)

    There is an algorithm now for calculating the nth digit of Pi at a whim.

    This is slightly retarded.

    • Re:silly (Score:5, Informative)

      by Trepidity (597) <delirium-slashdot AT hackish DOT org> on Tuesday January 05, 2010 @03:04AM (#30652348)

      As he points out himself, he doesn't really care about calculating digits of Pi; it's a convenient hook on which to hang an interesting algorithms challenge. From the FAQ:

      I am not especially interested in the digits of Pi, but in the various algorithms involved to do arbitrary-precision arithmetic. Optimizing these algorithms to get good performance is a difficult programming challenge.

      He also mentions elsewhere that of his code, "The most important part is an arbitrary-precision arithmetic library able to manipulate huge numbers stored on hard disks."

      • Yeah, it's more interesting how he exploited caching to good effect with his algorithm. This is not something we hear about all that often.
    • Re:silly (Score:4, Insightful)

      by David Jao (2759) <djao@dominia.org> on Tuesday January 05, 2010 @03:18AM (#30652428) Homepage

      There is an algorithm now for calculating the nth digit of Pi at a whim.

      The algorithm [wikipedia.org] only works for hexadecimal digits. There is no known formula or algorithm for calculating the n-th decimal digit directly.

      Having said that, the existence or non-existence of an n-th digit algorithm does not have any relevance on the silliness or non-silliness of computing trillions of digits of pi, unless the algorithm is extremely trivial (i.e. computing the digit takes less CPU time than a byte of I/O), which is not the case here.

      • Re:silly (Score:5, Informative)

        by Ambiguous Puzuma (1134017) on Tuesday January 05, 2010 @04:28AM (#30652842)

        There is no known formula or algorithm for calculating the n-th decimal digit directly.

        What about this [arxiv.org]?

        I present here a way of computing the nth decimal digit of pi (or any other base) by using more time than the [BBP] algorithm but still with very little memory.

        • Re: (Score:3, Informative)

          by David Jao (2759)

          There is no known formula or algorithm for calculating the n-th decimal digit directly.

          What about this [arxiv.org]?

          I present here a way of computing the nth decimal digit of pi (or any other base) by using more time than the [BBP] algorithm but still with very little memory.

          The algorithm you linked to requires cubic time in n. It hardly qualifies as "calculating the n-th decimal digit directly" given that the naive approach (calculating every single digit between 1 and n, and throwing away all but the last digit) is faster than cubic time.

          The only advantage of the algorithm you linked to is that it requires constant space.

    • Re: (Score:3, Interesting)

      by Bacon Bits (926911)

      Knowing how to calculate the nth digit of Pi itself is slightly retarded.

      The observable universe is about 50 billion light years across, which is about 4.27 * 10^26 meters. If we take a ring of atoms each roughly 1 Angstrom (10^-10 meters) apart with a diameter the size of the observable universe and want to determine the circumference of the resulting circle, then knowing Pi to 40 or so places is sufficient that the error caused by the atoms themselves is greater than that introduced by using an approxima

      • by krou (1027572)
        I thought it was 42 digits?
      • by Whiteox (919863)

        Knowing Pi to 40 or so places

        Face it, we all should know by now it's 42

      • by Stooshie (993666)
        That is a great engineering answer. Technically correct and calculated all the factors brilliantly.

        However Pi is not just used for measuring physical objects.


        An engineer, a physicist, and a mathematician were on a train heading north, and had just crossed the border into Scotland.

        The engineer looked out of the window and said "Look! Scottish sheep are black!"
        The physicist said, "No, no. Some Scottish sheep are black."
        The mathematician looked irritated. "There is at least one field, containing at le
    • by Tim C (15259)

      That's like saying that the fact that we have horses and cars, etc, make hiking or cycling anywhere retarded.

      Sometimes the point isn't the destination, it's the journey.

  • I believe in "Contact" (the book by Carl Sagan, not the movie), the travelers ask the superintelligent aliens "Do you believe in God? To which they reply: "Yes" When asked why, they say "We have proof" in the finding of a message in a transcendental number (pi?).

    After reading the Wikipedia summary I understand that when the travelers come home and are accused of fabricating the whole thing, one of them tries to "find" this message by running their own computer program. She finds a message, or does she?

    • How could you not?
      • Re: (Score:3, Funny)

        by Dahamma (304068)

        Exactly! And hence the discovery of our blessed lady of the grilled cheese sandwich...

        • by JustOK (667959)

          does it have bacon on it? It there was truly a god, the sandwich would have bacon on it.

    • Re: (Score:3, Funny)

      by ettlz (639203)
      Well given (I think, though may be wrong on this) that pretty much any finite sequence of digits will show up in the decimal expansion of pi at some point, there should be a raster image of a circle in 1s and 0s buried in it somewhere. Along with a greyscale raster of Goatse.
    • Re: (Score:3, Interesting)

      by ceoyoyo (59147)

      In any large enough collection of random numbers you will be guaranteed to find whatever pattern you're looking for, whether it's a hundred thousand zeros in a row or the text of the collected works of Shakespeare. You can test statistically how likely you are to find particular patterns in a collection of numbers of a particular size though.

      Finding patterns can be hard. If you have an idea of what you're looking for you can do much better than if you just want to find any pattern. SETI at Home has a pag

    • by Stooshie (993666)
      "(if you can call 2.7 trillion finite!)"

      erm, by definition it is finite!

      Interestingly, if someone has 2.7 trillion digits of Pi stored on their hard drive, they could actually have more than just a message. The may, unwittingly, be in possession of material that breaks copyright law! :-)
    • by mcgrew (92797) *

      The message was "We apologize for the inconvinience"

  • Too bad... (Score:5, Funny)

    by hallux.sinister (1633067) on Tuesday January 05, 2010 @03:54AM (#30652628)
    Only another four hundred billion decimal places, and they would have found the last one!

    ~Hal

  • Wasn't he the guy who developed lzexe ?

    Anyway, what's with surnames spelled in caps ? Does he say "I am fabrice" and then he screams "BELLARD" when stating his name ?

  • On his page with extracts of the digits of Pi [bellard.org], in the third column of the 799,999,951th digits, he's got a 2 where I think it should be a 5.

    ^_^

  • by Tjebbe (36955)

    I have just calculated a digit that's much further. It's 7, and it's somewhere around the 8 trillionth decimal. Give or take a few.

  • I don't think many people will be running his program that takes 116 days to complete to get as far as he did. Would have been nice to at least see how the code worked.

  • by stox (131684) on Tuesday January 05, 2010 @08:48AM (#30654054) Homepage

    in base pi. The answer was 10.

  • From TFA's technical notes: "Unfortunately, the RAM had no ECC (Error Correcting Code), so random bit errors could not be corrected nor detected. Since the computation lasted more than 100 days, such errors were likely [12]."

    Great we have all these digits, but they're mostly useless bits and their reliability is suspect.
  • Is zero. You can stop now.

  • Fabrice Bellard continues to amaze me.

An authority is a person who can tell you more about something than you really care to know.

Working...