Computing Pi

How well do Patterson's sequential and parallel methods of computing the quantity π/4 perform? Recall that the sequential method was to sum the infinite series for arctangent of one radian, while the parallel method was to compute the probability of a point falling within a unit circle when that point was randomly chosen from the square enclosing the unit circle.

To evaluate the sequential algorithm, let's look at its rate of convergence:

This rate of convergence is painfully slow: after ten iterations, we do not yet have even two decimal digits of π. A few centuries ago, John Machin derived a much faster series for π/4 based on the following formula:

Machin's series accumulates about 1.5 decimal digits per iteration:

So Patterson's choice of series for π/4 falls a bit short of recent practice, to say the least.

But what of his Monte Carlo parallel method? One can clearly build a good parallel program on it by having each of N tasks compute 1/N of the desired number of trials, and then combining their results. Increasing the desired number of trials will drive the parallel communication overhead down to an arbitrarily low level. So scalability of Patterson's Monte Carlo method is nothing short of excellent.

But scalability is only part of the problem to be solved. Raw performance is also critically important.

To analyze this method's performance, consider that the first trial will either be within the unit circle (which gives the estimate π=4) or outside of it (which gives the estimate π=0). The second trial adds the possibility of the estimate π=2. After ten trials, we might possibly have an estimate as good as π=3, or one digit. After one hundred trials, we might (or might not) have an estimate as good as π=3.1.

Continuing this line of thought:

Attaining the 15-digit accuracy that Machin's formula delivered after only 10 iterations thus requires at least one quadrillion trials. Therefore, if we had a 1,000-CPU system that could do one trial per nanosecond, it would take more than 15 minutes to compute π to at most 15 places. In contrast, my laptop system took 20 milliseconds to compute this same accuracy using Machin's formula, even with the performance penalty imposed by the bc interpretor. In short, when doing mathematics with parallel computers, you need not only good parallel design, but also good mathematics. Patterson's approach scores quite highly in the parallel-design department, but falls short in the good-mathematics department.

That said, Machin lived centuries ago. What is the state of the art of computing π in 2010?

As of this writing, the effort that has computed the most digits of π on a desktop system used y-cruncher, which, for the record, is a parallel program. The Chudnovsky formula, which delivers 14 decimal digits per iteration, and is based on earlier work by Ramanujan, was used for the computation.

So, once again, attaining good performance and scalability requires not just good parallel design, but also good mathematics.