 |
Recently
on MathTrek:
The Limits of Mathematics -- 2/21/98 The Counterfeit Coin -- 2/14/98 Nine Primes in a Row -- 2/7/98
|
February 28, 1998
Pick a Digit, Any Digit
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 40 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:
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. Details are available atComputing 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 Supérieure des Télécommunications in Paris, 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/k2k.
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.
Mathematically, the big question is whether a similar approach could be used to compute individual decimal digits of such numbers as pi. "We're decimal creatures," Borwein remarks. "It would be an order of magnitude more stirring to compute decimal digits in this way."
References:
Bailey, D., P. Borwein, and S. Plouffe. In press. On the rapid computation of various polylogarithmic constants. Mathematics of Computation. (Available at http://www.cecm.sfu.ca/personal/pborwein/PISTUFF/Apistuff.html.)
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.
Details of the Bailey-Borwein-Plouffe pi algorithm are available at http://www.mathsoft.com/asolve/plouffe/plouffe.html.
You can find out more about Catalan's constant at http://www.mathsoft.com/asolve/constant/catalan/catalan.html or http://mathworld.wolfram.com/CatalansConstant.html.
Fabrice Bellard describes his pi computations at http://www-stud.enst.fr/~bellard/pi-challenge/.
Comments are welcome. Please send messages to Ivars Peterson at ip@sciserv.org.
Ivars Peterson is the mathematics and physics writer and on-line editor at Science News. He is the author of The Mathematical Tourist, Islands of Truth, Newton’s Clock, Fatal Defect, and *The Jungles of Randomness: A Mathematical Safari. His current works in progress are an updated, 10th anniversary edition of The Mathematical Tourist (to be published in 1998 by W.H. Freeman) and Fragments of Infinity: A Kaleidoscope of Mathematics and Art (to be published in 1999 by Wiley).
*NOW AVAILABLE: The Jungles of Randomness: A Mathematical Safari by Ivars Peterson. New York: Wiley, 1997. ISBN 0-471-16449-6. $24.95 US.
copyright 1998 Science Service