Computing π with Hadoop

The results below are obsoleted. Please see arXiv:1008.3171 for the latest results.

I used Hadoop in Yahoo! to compute π, more specifically, the nth bit of π. A map-reduce program, called distbbp, was developed for such purpose. It has been checked in to Hadoop 0.21 as an example program, so that the entire program is publicly available. The results are shown in the table on the right.

  • Except for the first and the last rows, bits starting at positions n4 and n+4 are also computed for the sake of correctness.
  • Row 0 to Row 7
    • They were computed by a single machine.
    • A single run of Row 7 took several seconds.
  • Row 8 to Row 14
    • They were computed by a 7600-CPU-core cluster.
    • A single run of Row 14 took 27 hours.
    • The computations in Row 13 and Row 14 were completed on May 20, 2009. It seems that the corresponding bits were never computed before.
  • The first part of Row 15 (6216B06)
    • The first 30% of the computation was done in idle cycles of some clusters spread over 20 days.
    • The remaining 70% was finished over a weekend on Hammer, a 30,000-CPU-core cluster, which was also used for the petabyte sort benchmark.
    • The log files are available here.
    • The result was posted in this YDN blog.
  • The second part of Row 15 (D3611)
    • The starting position is 1,000,000,000,000,053, totally 20 bits.
    • Two computations, at positions n and n+4, were performed.
    • A single computation was divided into 14,000 jobs and totally 7,000,000 tasks. It took 208 years of CPU-time or 12 days of cluster (with 7600-CPU-core) time.
    • The log files are available here.
    • The computations were completed on June 30, 2009. The last bit, the 1,000,000,000,000,072nd bit, probably is the highest bit (or the least significant bit) of π computed at that time.
Position nπ bits (in hex) starting at n
151,000,000,000,000,0016216B06 ... D3611

* By representing π in decimal, hexadecimal and binary, we have

    π=3.1415926535 8979323846 2643383279 ...
    =3.243F6A8885 A308D31319 8A2E037073 ...
    =11.0010010000 1111110110 1010100010 ...
The first ten bits of π are 0010010000.