BBP Algorithm for Pi

摘要

The 'Bailey-Borwein-Plouffe' (BBP) algorithm for (pi) is based on the BBP formula for (pi), which was discovered in 1995 and published in 1996 (3): (pi) = (summation)(sub k=0)(sup (infinity)) 1/16(sup k) (4/8k+1 - 2/8k+4 - 1/8k+5 - 1/8k+6). This formula as it stands permits (pi) to be computed fairly rapidly to any given precision (although it is not as efficient for that purpose as some other formulas that are now known (4, pg. 108-112)). But its remarkable property is that it permits one to calculate (after a fairly simple manipulation) hexadecimal or binary digits of (pi) beginning at an arbitrary starting position. For example, ten hexadecimal digits (pi) beginning at position one million can be computed in only five seconds on a 2006-era personal computer. The formula itself was found by a computer program, and almost certainly constitutes the first instance of a computer program finding a significant new formula for (pi). It turns out that the existence of this formula has implications for the long-standing unsolved question of whether (pi) is normal to commonly used number bases (a real number x is said to be b-normal if every m-long string of digits in the base-b expansion appears, in the limit, with frequency b(sup -m)). Extending this line of reasoning recently yielded a proof of normality for class of explicit real numbers (although not yet including (pi)) (4, pg. 148-156).