| | Ivars Peterson's MathTrek |
March 2, 1998
One of the most amazing mathematical results of the last few years was the discovery of a surprisingly simple formula for computing digits of the number pi. Unlike previously known methods, this one allows you to calculate isolated digits - - without computing and keeping track of all the preceding numbers.
No one had previously even conjectured that such a digit-extraction algorithm for pi was possible, says Steven Finch of MathSoft, Inc., in Cambridge, Mass.
The only catch is that the formula works for hexadecimal (base 16) or binary digits but not for decimal digits. Thus, it's possible to determine that the forty billionth binary digit of pi is 1, followed by 00100100001110. . . . However, there's no way to convert these numbers into decimal form without knowing all the binary digits that come before the given string.
In hexadecimal form, the number pi is written as 3.243F6A8885A308D313198A2E0. . . , where the letters stand in for the hexadecimal equivalent of the base-10 numbers 10 (A), 11 (B), 12 (C), 13 (D), 14 (E), and 15 (F). It's straightforward to convert a hexadecimal expression into binary form but not into decimal form.
The novel scheme for computing individual hexadecimal digits of pi was found by David H. Bailey of the NASA Ames Research Center in Mountain View, Calif., Peter B. Borwein of Simon Fraser University in Burnaby, British Columbia, and Simon M. Plouffe, now at the University of Quebec in Montreal.
The method is based on the following new formula for pi:
Computing individual hexadecimal digits using that formula relies on a venerable technique known as the binary algorithm for exponentiation. Bailey, Borwein, and Plouffe provide details of how that procedure works in a soon-to-be-published report titled "On the rapid computation of various polylogarithmic constants."
A year after the discovery of the formula, Fabrice Bellard, a student at the Ecole Nationale Superieure des Telecommunications in Paris, France, used it to calculate the100 billionth hexadecimal digit of pi: 9, followed by C381872D2. . . . Last September, he computed the trillionth digit: 8, followed by 7F72B1DC. . . . In binary form, the corresponding result is 1, followed by 000011111110111. . . . The main calculation required a month of computation on more than 20 workstations and personal computers.
The basic Bailey-Borwein-Plouffe algorithm can also be used to compute the nth digit of certain other transcendental numbers, such as log(2) and (pi)^2. Log(2), for example, can be determined from the series: 1/2 + 1/8 + 1/18 + . . ., where the kth term is 1/k2^k.
Recently, physicist David John Broadhurst of the Open University in Milton Keynes, England, reported the discovery of formulas for determining isolated hexadecimal or binary digits of several additional numerical constants of considerable interest to mathematicians, including Catalan's constant, zeta(3), and zeta(5).
"It's a spectacular piece of work," says Simon Fraser's Jonathan Borwein. "His tools were a marvellous combination of experiment, numeric and symbolic computation, followed by a mix of computer and human proofs."
The decimal digits of Catalan's constant, named for the Belgian mathematician Eugène Charles Catalan (1814-1894), can be calculated from the series: 1 - 1/9 + 1/25 - 1/49 + . . ., where the kth term is (-1)^k/(2k + 1)^2. Broadhurst found a formula that could be used to obtain isolated hexadecimal and binary digits. Interestingly, mathematicians have not yet proved that Catalan's constant (0.915965594177. . .) is an irrational number - - that is, not expressible as a fraction, or rational number. The number itself is now known to 12.5 million decimal digits.
"It illustrates that there's a world of difference between being able to come up with methods of computing a constant quickly and necessarily being able to prove something about its transcendance or irrationality," Borwein says. "This highlights the difference between what we can prove, what we have good evidence for, and what we just know is true even though a proof appears hopelessly out of our reach."
What apparently makes it feasible to find formulas for certain constants and not others is that each successfully tackled number, including pi, is the value of a logarithm, Borwein says. Broadhurst's interest in the formulas lies in the context of applying the theory of mathematical knots to physics, specifically quantum field theory.
Plouffe, for one, has found a way to compute individual decimal digits of pi without calculating preceding digits. That makes it possible to compute a particular decimal digit of pi using a pocket calculator, Plouffe says. However, his algorithm is fairly slow and clearly impractical for determining the millionth or billionth decimal digit of pi.
Nonetheless, there's no evidence yet that an efficient algorithm for computing isolated decimal digits of pi doesn't exist.
Copyright 1998 by Ivars Peterson
Bailey, D., P. Borwein, and S. Plouffe. In press. On the rapid computation of various polylogarithmic constants. Mathematics of Computation.
Bailey, D.H., et al. 1997. The quest for pi. Mathematical Intelligencer 19(No. 1):50.
Blatner, D. 1997. The Joy of Pi. New York: Walker. (See http://www.joyofpi.com.)
Peterson, I. 1995. A new formula for picking off pieces of pi. Science News 148(Oct. 28):279.
Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.