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:
  • One thing to say (Score:5, Informative)

    by DirtyCanuck (1529753) on Tuesday January 05, 2010 @03: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 Trepidity (597) <delirium-slashdotNO@SPAMhackish.org> on Tuesday January 05, 2010 @03: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 @03: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
  • Re:silly (Score:5, Informative)

    by Trepidity (597) <delirium-slashdotNO@SPAMhackish.org> on Tuesday January 05, 2010 @04: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."

  • Re:So... umm... (Score:4, Informative)

    by Trepidity (597) <delirium-slashdotNO@SPAMhackish.org> on Tuesday January 05, 2010 @04:08AM (#30652366)

    He mentions in the "press release" page that the most important thing developed in his code is "an arbitrary-precision arithmetic library able to manipulate huge numbers stored on hard disks", which sounds basic-research-y. There's some more on that in the technical-details PDF, although unfortunately he says he doesn't plan to release the code (somewhat unusual, since most of his projects are free software).

  • Re:Verification (Score:4, Informative)

    by msclrhd (1211086) on Tuesday January 05, 2010 @04: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.

  • by msclrhd (1211086) on Tuesday January 05, 2010 @04:28AM (#30652492)

    He also wrote the Obfuscated Tiny C Compiler (http://bellard.org/otcc/) in 2002 for the Obfuscated C contest, where otcc could compile itself. This became the Tiny C Compiler (TCC) which was picked up by Robert Landley (but subsequently dropped a while later) that is a capable, fast C90/C99 compiler.

    His projects page (http://bellard.org/) and the older projects (http://bellard.org/projects.html) contain a lot of interesting projects.

    Also of note: Fabrice achieved the record for Pi computation in 1997 as well:
          http://bellard.org/pi/pi_hexa.html [bellard.org]
          http://bellard.org/pi-challenge/announce220997.html [bellard.org]
          http://bellard.org/pi/ [bellard.org]

  • Re:So.... (Score:2, Informative)

    by Fjodor42 (181415) on Tuesday January 05, 2010 @04:49AM (#30652596) Homepage

    Read... The... Fine... (wait for it) Article!

    Spoiler alert!

    He developed a highly efficient library for arbitrary precision floating-point number calculations, capable of having a desktop machine best a supercomputer. Now go change your signature to "For lack of a better question..." ;-)

  • Re:silly (Score:5, Informative)

    by Ambiguous Puzuma (1134017) on Tuesday January 05, 2010 @05: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.

  • by l0b0 (803611) on Tuesday January 05, 2010 @06:00AM (#30652970) Homepage

    He will be releasing the program he created for Windows (64bit only) and Linux

    PS: Not the source [bellard.org]

  • Re:fabrice BELLARD (Score:1, Informative)

    by Anonymous Coward on Tuesday January 05, 2010 @06:22AM (#30653066)

    I read something recently on this, it's (apparently) a French convention, presumably to make it clear which name is the surname. I don't know much about it, just something I saw on the Planet Debian RSS:

    http://gwolf.org/blog/internationalizing-your-local-customs [gwolf.org]

  • Re:So... umm... (Score:5, Informative)

    by JasterBobaMereel (1102861) on Tuesday January 05, 2010 @07:02AM (#30653236)

    Basic research ..... you know that stuff that has no useful application now .....especially maths

    Like group theory, invented in 1832 by Évariste Galois, had no really useful application until the mid 20th century ... Now quantum mechanics and so most of modern electronics uses it ....

  • Re:One thing to say (Score:0, Informative)

    by Anonymous Coward on Tuesday January 05, 2010 @07:09AM (#30653276)

    we never really cared about the usage of "trick". What we cared about is the usage of "hide the decline". THATS the part that we want to understand, and still hasn't been explained... they just keep explaining the use of "trick".

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

    in base pi. The answer was 10.

  • Re:silly (Score:3, Informative)

    by David Jao (2759) <djao@dominia.org> on Tuesday January 05, 2010 @12:58PM (#30656680) Homepage

    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.

Save energy: Drive a smaller shell.

Working...