Search This Blog

24 January 2011

a modest achievement by sentient Earth humans: we expand Pi to trillions of decimal digits!

Click to enlarge Chudnovsky Formula

We know -- yes, with certainty -- that we're not alone as the only intelligent organic species in our
Nilky Way Galaxy. We share the Melkweg with tens of thousands of intelligent civilizations. Here on Earth, using radio, we search for others, and we could, within decades, get lucky and tune in on some her Mozart or some other Hawking, at long last answering the ancient, haunting question: Are we

But as other SETI races tune in on Earth's radio transmissions -- listen to our music, decode our alphabetic text, read our novels and our poetry -- they have chosen a sad era to make contact with their intelligent neighbors. For in this era, they are watching MTV's "Skins" as a representative of Earth sentient culture.

And they are learning about an Earth whose noisiest achievement is a race for more nations and Non-State-Actors to develop nuclear weapons and delivery systems to send them halfway across Earth and detonate them against humans we hate for religious or political reasons.

And on the conventional warfare side, Earth's greatest sovereign superpower is waging two wars in Asia - in Iraq and in Afghanistan -- both wars dragging on longer than World War Two, neither war with an end in sight.

Embarrassing, shameful, frightening -- that we have learned so much, and done such pathetic things with it. Our neighbors in the Milky Way, eavesdropping on us, decoding us ...

It's mostly bad, car bombs, oaths to annihilate one another ... this is the focus of human brilliance ...

But it's not all bad. It's not all Embarrassment Earth. Here on Earth, 2010 wasn't entirely a race to blow ourselves up on market day, a race to fill up hospital wards with maimed children -- on orders from God, who goes by a variety of aliases.

* * *

Late in 2010, sentient races in the Milky Way would have eavesdropped on this modest achievement by human beings who, just like us, live on Earth. Using desktop computers -- modest boxes just like yours and mine -- human beings used a mathematical equation and expanded the digital decimal expression of the ratio pi into TRILLIONS of decimal digits. (And won a mention in the Guinness Book of World Records for their efforts.)

The same planet that spends most of its time trying to murder thousands of its citizens, on orders from Allah, Eloheynu, Jesus ... some of us have better things to do. Rather than make home-brew high explosives, some of us find the precise ratio between the circle's circumference and its diameter.

In an environment entirely free of hate, in a zone free of killing, we ask the deepest questions about the fundamental riddles of mathematics.

Here, on Planet Mozart, we did something brilliant and beautiful again, and not a single explosion, not a single wound, not a single corpse.

Don't get the wrong idea. There are a lot of mathematicians on Earth who think that expanding the decimal expression of pi to trillions of places is ridiculous, worthless, useless, mathematical nonsense. There are lots of brilliant professional mathematicians who think the Chudnovsky Brothers, using an equation from around 1910 by the self-taught Hindu mathematician Ramanujan, have accomplished ... well, nothing.

I'm not one of them. The Chudnovsky Brothers, with Ramanujan's equation, and not a single human corpse, took a fundamental mathematical puzzle farther than the most brilliant human beings had ever taken the question before.

However far we got with this question, it's worth a delicious Guinness stout, and a mention in the Guinness Book of World Records.

It's worth a grafitti scrawl on Earth for what we did, and we did it entirely non-violently.


5 Trillion Digits of Pi - New World Record -- Pushing the limits of personal computing ... How much further can we go?

By Alexander J. Yee & Shigeru Kondo

(Last updated: September 26, 2010)

This is a followup to our previous announcement of our computation of 5 trillion digits of Pi. This article details some of the methods that were used for the computation as well as the hardware and the full timeline of the computation.

Some of you knew this was coming... It was just a matter of when. (and how many digits)

Although we were very quiet about this computation while it was running, anyone who followed my website or my XtremeSystems thread between February and May would have easily guessed that we were attempting a world record.

1415926535 8979323846 2643383279 5028841971 6939937510 : 50
5820974944 5923078164 0628620899 8628034825 3421170679 : 100
2962457053 9070959679 6673211870 6342459769 2128529850 : 999,999,999,950
2976735807 0882130902 2460461146 5810642210 6680122702 : 1,000,000,000,000
9354516713 6069123212 1286195062 3408400370 1793492657 : 1,999,999,999,950
8386341797 9368318191 5708299469 1313121384 3887908330 : 2,000,000,000,000
3840840269 5893047555 2627475826 8598006396 3215856883 : 2,699,999,989,950
9256371619 3901058063 3448436720 6294374587 7597230153 : 2,699,999,990,000
8012497961 5892988915 6174704230 3863302264 3931687863 : 2,699,999,990,050
3126006397 8582637253 6739664083 9716870851 0983536511 : 2,699,999,990,100
5628334110 5221005309 8638608325 4364661745 5833914321 : 2,999,999,999,950
9150024270 6285788691 0228572752 8179710957 7137931530 : 3,000,000,000,000
5209957313 0955102183 1080456596 1489168093 0578494464 : 3,999,999,999,950
3638467628 3610607856 5071920145 5255995193 8577295739 : 4,000,000,000,000
2597691971 6538537682 7963082950 0909387733 3987211875 : 4,999,999,999,950
6399906735 0873400641 7497120374 4023826421 9484283852 : 5,000,000,000,000

Click here for access to some of the digits.


    * Numberworld Home
    * Computation Statistics
    * Purpose... Why?
    * The Software: y-cruncher -
      A Multi-threaded Pi Benchmark
    * Contributing Computers
    * Formulas Used for Computation  
    * Sufficiency of Verification
    * Arithmetic Algorithms
    * Maximizing Scalability
    * Error-Detection and Correction
    * Checkpointing + Restartability
    * Opportunities for Improvement
    * Detailed Timeline (With Screenshots)
    * Frequently Asked Questions
    * Special Thanks
    * About Me
    * Questions or Comments

Computation Statistics - All times are Japan Standard Time (JST).

Here are the full computation statistics. As with all significant computations that are done using y-cruncher - A Multi-Threaded Pi Program, a screenshot and validation is included. Since the computation was done in multiple sessions, there is no single screenshot that captures the entire computation from start to finish. The screenshot provided here is simply the one that shows the greater portion of the computation.

The main computation took 90 days on Shigeru Kondo's desktop. The computer was dedicated for this task.

Over the course of the computation, one error was detected and corrected via software ECC. Since the error was corrected, the final results are not affected. The computation error is believed to be caused by a hardware anomaly, or by hardware instability.

Due to the size of this computation, a tremendous amount of memory was needed:

  - Roughly 22 TB* of disk was needed to perform the computation.

  - Another 3.8 TB of disk was needed to store the compressed output of decimal and hexadecimal digits.

If the digits were stored in an uncompressed ascii text file, the combined size of the decimal and hexadecimal digits would be 8.32 TB.

*All units used in this article are binary:

GB = 230 bytes

TB = 240 bytes
Pi - Computation
90 days
Start :  6:19 PM (JST) May 4, 2010
Finish:  1:12 AM (JST) August 3, 2010
Pi - Verification
64 hours (Primary - Bellard's BBP)
66 hours (Secondary - Plouffe's BBP)
Start :  See Detailed Timeline
Finish:  See Detailed Timeline

Computation Step     Time
Series Summation:     73 days
Square Root:     63.3 hours
Final Multiply:     41.6 hours
Base Conversion:     8.2 days
Verify Base Conversion:     45.6 hours
Total Time*:     90 days

Validation File: Validation - Pi - 5,000,000,000,000.txt

Note that the multicore efficiency % is inaccurate. The actual efficiency is about ~85%.

*The total time also includes the time needed to output the digits to disk as well as the time needed to recover from the computational error.

For a detailed timeline of events related to this computation, see here.

Purpose... Why?

Because it's Pi... and because we can!

On a more serious note:

After Fabrice Bellard's announcement of 2.7 trillion digits on a "relatively cheap" desktop, it was pretty clear that the limit of personal computing was a lot higher.

Shigeru Kondo and I wanted to see how much better we could do if we used some more powerful hardware.

Both of us are hardware fanatics. And both of us (especially Shigeru Kondo) had some very powerful machines at our disposal.

So with that, we decided to see how far we could push the limits of personal computing using personally owned hardware.

Unlike Fabrice Bellard's record which focused on efficiency and getting the most out of a small amount of hardware. Our computation focused more on getting the most performance and scalability from a LOT of hardware.

How much hardware can we cram into one machine and still make it faster?

The main challenge for a computation of such a size, is that both software and hardware are pushed beyond their limits.

For such a long computation and with so much hardware, failure is not just a probability. It is a given. There are simply too many components that can fail.

So the questions become:

    * How much can the hardware be expanded while maintaining an acceptable level of reliability?

    * Is it possible to build enough fault-tolerance into the software to cover for hardware failure?

Hardware: Shigeru Kondo's Desktop

Shigeru Kondo's computer had the following specifications:

    2 x Intel Xeon X5680 @ 3.33 GHz - (12 physical cores, 24 hyperthreaded)
    96 GB DDR3 @ 1066 MHz - (12 x 8 GB - 6 channels) - Samsung (M393B1K70BH1)
    Asus Z8PE-D12
Hard Drives
    1 TB SATA II (Boot drive) - Hitachi (HDS721010CLA332)
    3 x 2 TB SATA II (Store Pi Output) - Seagate (ST32000542AS)
    16 x 2 TB SATA II (Computation) - Seagate (ST32000641AS)
Raid Controller
    2 x LSI MegaRaid SAS 9260-8i
Operating System
    Windows Server 2008 R2 Enterprise x64


Software: y-cruncher - A Multi-Threaded Pi Program/Benchmark

Software for Computation:

The program that was used for the main computation is y-cruncher v0.5.4.9138 Alpha.

See main page: y-cruncher - A Multi-Threaded Pi Program

y-cruncher is a powerful multi-threaded program/benchmark that is becoming an increasingly popular tool within the computer enthusiast community. As of this writing, it also holds the world record for most digits computed for several other famous constants. (These include: e, Square Root of 2, Golden Ratio, Euler-Mascheroni Constant, Natural Log of 2, Apery's Constant, and Catalan's Constant.)

There are several aspects of y-cruncher that set it apart from most other similar Pi-crunching programs:

    * It uses state-of-the-art algorithms to achieve never-before-seen computational speeds. Many of these methods and algorithms are newly developed and first-time tested in y-cruncher. Therefore they are not yet used by other programs.
    * y-cruncher is scalable to many cores. Most other multi-threaded Pi programs do not scale well beyond several cores and are unable to fully utilize many core machines such as the 12-core/24-thread computer that was used for this Pi computation.
    * y-cruncher supports the use of multiple hard drives to use as distributed memory storage for very large computations.
    * y-cruncher is fault-tolerant to hardware errors. It is able to detect and recover from minor computational errors that are caused by hardware anomalies or instablity. This is important for extremely long computations where the chance of hardware failure is non-negligible.

The exact version that was used for the computation is:

y-cruncher v0.5.4.9138 Alpha (PB) - x64 SSE4.1 ~ Ushio

This version was a very early private-beta for v0.5.4. It was slightly modified to display more detail on the progress of the computation. (All public versions display only a percentage.)

Software for Verification:

The program that was used for the verification is y-cruncher BBP v1.0.119.

See main page: y-cruncher BBP

This program implements the digit-extraction algorithm for Pi using the BBP formulas. It's sole purpose was to verify the main computation.

Both programs are written by me (Alexander J. Yee) and are available for download from their respective pages.

For those who have used y-cruncher before and are curious at how it works:

This webpage is the first article I have written that reveals significant details on the inner workings of y-cruncher... Enjoy!

No comments: