In this paper, Takahashi describes an apparently impressive computation, of 2.576 x 10¹² decimal digits of &pgr;, in 29 hours on a 10240-core parallel processor with 16384 GB of memory. Note that, at its most efficient, the storage of that many digits of &pgr; requires 996 GB of memory, and 1200 GB as the author stores it (eight decimal digits in a 32-bit word). The computation was done with a modification of the Gauss-Legendre (arithmetic/geometric mean) algorithm due to [1], and was completely checked using the Borweins’ method [2], another quartically convergent method, in 44 hours. Both algorithms run in time O(M(n)log n) for n digits, where M(n) is the time taken to multiply n-digit numbers.

I say “apparently impressive” since Bellard [3] describes the computation of 2.7 x 10¹² decimal digits of &pgr; in 131 days on a single four-core 6 GB computer. The author of this paper, therefore, took 24 times the core-hours and 25 times the GB-hours. Another computation [4] (too late to be cited in the paper) computed 5 x 10¹² decimal digits of &pgr; in 90 days on a 12-core 96 GB processor. Linear scaling by the number of digits shows the paper under review to have used 22 times the core-hours and six times the GB-hours of this computation. Both of these used another algorithm [5], whose running time is O(log²(n)M(n)). It is noteworthy that both these computations were manipulating individual numbers that were larger, by a factor of 160 and 10 respectively, than their main memory.

Hence, the interesting question is why the computation under review uses so many more resources than the ones mentioned above, despite apparently using a more efficient algorithm. In answer to this, note what Brent and Zimmermann [6] say of the O(M(n)log n) Gauss-Legendre method: “The implied constant here can be quite large, so other methods are better for small n.”

Another clue is the fact that the computation used base 10⁸, while the others used binary bases. Bellard [3] quotes 12 days of the 130 going into the binary-decimal conversion. This is a smaller overhead than the increase in number of words of memory used, caused by the decimal base in this paper.

Perhaps the most significant point is in section 5.2 of this paper, where it explains that during the fast Fourier transform (FFT), a 10⁸ digit is split into two 10⁴ digits, each stored in 64 bits. This increases the storage requirements to 4798 GB for a single number, and makes FFT-based multiplication impossible in the 17.5 TB of main memory available. Hence, the author was forced to manipulate numbers of one-fourth the desired size, and to use two layers of Karatsuba multiplication (that is, nine multiplications of ¼-sized numbers) to combine them. This alone costs a factor of 2.145.

In short, this paper is an eloquent testimony to the fact that constants do matter, and O isn’t everything.