BBP 公式 (Bailey–Borwein–Plouffe formula)是 1995 年由 David H. Bailey、Peter B. Borwein 和 Simon Plouffe 发现的一种 π \piπ 的计算公式。它最引人注目的特性是:可以计算 π \piπ 的任意二进制或十六进制位,而不需要计算前面的所有位 。
这一特性在数学和计算机科学中具有里程碑意义——在 BBP 之前,计算 π \piπ 的第 n nn 位需要先算出前 n − 1 n-1n − 1 位。BBP 颠覆了这一认知。
π = ∑ k = 0 ∞ 1 16 k ( 4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6 ) \pi = \sum_{k=0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right)π = k = 0 ∑ ∞ 1 6 k 1 ( 8 k + 1 4 − 8 k + 4 2 − 8 k + 5 1 − 8 k + 6 1 )
1995 年,Bailey 正在运行一个称为 PSLQ(整数关系检测算法)的程序,尝试寻找形如
π = ∑ k = 0 ∞ 1 b k ∑ j = 1 m a j m k + j \pi = \sum_{k=0}^{\infty} \frac{1}{b^k} \sum_{j=1}^{m} \frac{a_j}{mk + j}π = k = 0 ∑ ∞ b k 1 j = 1 ∑ m mk + j a j
的公式。经过几天的计算,程序输出了 BBP 公式——以 π = 3.14159 … \pi = 3.14159\ldotsπ = 3.14159 … 为输入,算法自动发现了这个以前未知的恒等式。
方面
影响
数学革命
BBP 公式首次证明可以在常数时间和空间内提取 π \piπ 的任意十六进制位
分布式计算
催生了基于 BBP 公式的分布式 π \piπ 计算项目,如 PiHex
正规数猜想
BBP 公式为 π \piπ 的二进制随机性提供了间接证据
算法创新
催生了 "spigot algorithms"(水龙头算法)的概念
BBP 公式的标准形式为:
π = ∑ k = 0 ∞ 1 16 k ( 4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6 ) \pi = \sum_{k=0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right)π = k = 0 ∑ ∞ 1 6 k 1 ( 8 k + 1 4 − 8 k + 4 2 − 8 k + 5 1 − 8 k + 6 1 )
其中 k kk 从 0 00 开始,每一项的权重是 1 16 k \frac{1}{16^k}1 6 k 1 ,即十六进制下的位置权重。
为了直观理解公式的收敛速度,我们计算前几项:
k kk
权重 1 / 16 k 1/16^k1/1 6 k
4 / ( 8 k + 1 ) 4/(8k+1)4/ ( 8 k + 1 )
2 / ( 8 k + 4 ) 2/(8k+4)2/ ( 8 k + 4 )
1 / ( 8 k + 5 ) 1/(8k+5)1/ ( 8 k + 5 )
1 / ( 8 k + 6 ) 1/(8k+6)1/ ( 8 k + 6 )
单次项值
部分和
0
1.00000000
4.00000000
0.50000000
0.20000000
0.16666667
3.13333333
3.13333333
1
0.06250000
0.44444444
0.16666667
0.07692308
0.07142857
0.00808914
3.14142247
2
0.00390625
0.23529412
0.10000000
0.04761905
0.04545455
0.00016492
3.14158739
3
0.00024414
0.16000000
0.07142857
0.03448276
0.03333333
0.00000501
3.14159240
4
0.00001526
0.12121212
0.05555556
0.02702703
0.02631579
0.00000019
3.14159259
5
0.00000095
0.09756098
0.04545455
0.02222222
0.02173913
0.00000001
3.14159265
可以看到,仅 5 项就得到了 π \piπ 的小数点后 7 位精度 (3.14159265 3.141592653.14159265 ),收敛速度非常快。
BBP 公式有许多变体,适用于不同的底数和不同的数学常数:
∑ k = 0 ∞ p ( k ) b k q ( k ) \sum_{k=0}^{\infty} \frac{p(k)}{b^k q(k)}k = 0 ∑ ∞ b k q ( k ) p ( k )
其中 p ( k ) p(k)p ( k ) 和 q ( k ) q(k)q ( k ) 是整数多项式,b bb 是计算底数(通常为 2 的幂)。
常数
BBP 型公式
发现者
π 2 \pi^2π 2
∑ k = 0 ∞ 1 16 k ( 16 ( 8 k + 1 ) 2 − 16 ( 8 k + 2 ) 2 − 8 ( 8 k + 3 ) 2 − 16 ( 8 k + 4 ) 2 − 4 ( 8 k + 5 ) 2 − 4 ( 8 k + 6 ) 2 + 2 ( 8 k + 7 ) 2 ) \displaystyle\sum_{k=0}^{\infty} \frac{1}{16^k} \left( \frac{16}{(8k+1)^2} - \frac{16}{(8k+2)^2} - \frac{8}{(8k+3)^2} - \frac{16}{(8k+4)^2} - \frac{4}{(8k+5)^2} - \frac{4}{(8k+6)^2} + \frac{2}{(8k+7)^2} \right)k = 0 ∑ ∞ 1 6 k 1 ( ( 8 k + 1 ) 2 16 − ( 8 k + 2 ) 2 16 − ( 8 k + 3 ) 2 8 − ( 8 k + 4 ) 2 16 − ( 8 k + 5 ) 2 4 − ( 8 k + 6 ) 2 4 + ( 8 k + 7 ) 2 2 )
Bailey
ln 2 \ln 2ln 2
∑ k = 1 ∞ 1 k ⋅ 2 k \displaystyle\sum_{k=1}^{\infty} \frac{1}{k \cdot 2^k}k = 1 ∑ ∞ k ⋅ 2 k 1
经典的泰勒级数
arctan ( 1 / 2 ) \arctan(1/2)arctan ( 1/2 )
∑ k = 0 ∞ ( − 1 ) k ( 2 k + 1 ) ⋅ 2 2 k + 1 \displaystyle\sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1) \cdot 2^{2k+1}}k = 0 ∑ ∞ ( 2 k + 1 ) ⋅ 2 2 k + 1 ( − 1 ) k
反正切级数
π 3 \pi\sqrt{3}π 3
∑ k = 0 ∞ 1 5 k ( 4 5 k + 1 − 1 5 k + 2 − 1 5 k + 3 + 1 5 k + 4 ) \displaystyle\sum_{k=0}^{\infty} \frac{1}{5^k} \left( \frac{4}{5k+1} - \frac{1}{5k+2} - \frac{1}{5k+3} + \frac{1}{5k+4} \right)k = 0 ∑ ∞ 5 k 1 ( 5 k + 1 4 − 5 k + 2 1 − 5 k + 3 1 + 5 k + 4 1 )
Bailey
π 2 \pi\sqrt{2}π 2
∑ k = 0 ∞ 1 8 k ( 4 8 k + 1 − 2 8 k + 3 − 1 8 k + 5 − 1 8 k + 7 ) \displaystyle\sum_{k=0}^{\infty} \frac{1}{8^k} \left( \frac{4}{8k+1} - \frac{2}{8k+3} - \frac{1}{8k+5} - \frac{1}{8k+7} \right)k = 0 ∑ ∞ 8 k 1 ( 8 k + 1 4 − 8 k + 3 2 − 8 k + 5 1 − 8 k + 7 1 )
Bailey
Spigot(水龙头)算法的名字形象地说明了它的工作方式——就像打开水龙头获取水一样,你可以直接取到第 n nn 位数字 ,而不需要等待前面的水(数字)先流完。
BBP 公式实现直接位提取的关键步骤如下:
第 1 步:乘 16 n 16^n1 6 n
要获取第 n nn 位(十六进制),将 BBP 公式两边乘以 16 n 16^n1 6 n :
16 n π = ∑ k = 0 ∞ 16 n − k 16 k ( 4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6 ) 16^n \pi = \sum_{k=0}^{\infty} \frac{16^{n-k}}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)1 6 n π = k = 0 ∑ ∞ 1 6 k 1 6 n − k ( 8 k + 1 4 − 8 k + 4 2 − 8 k + 5 1 − 8 k + 6 1 )
第 2 步:拆分求和
将求和拆分为前 n nn 项和后 n nn 项:
16 n π = ∑ k = 0 n 16 n − k 8 k + 1 + ∑ k = n + 1 ∞ 16 n − k 8 k + 1 − 2 ∑ k = 0 n 16 n − k 8 k + 4 − 2 ∑ k = n + 1 ∞ 16 n − k 8 k + 4 − ⋯ 16^n \pi = \sum_{k=0}^{n} \frac{16^{n-k}}{8k+1} + \sum_{k=n+1}^{\infty} \frac{16^{n-k}}{8k+1} - 2\sum_{k=0}^{n} \frac{16^{n-k}}{8k+4} - 2\sum_{k=n+1}^{\infty} \frac{16^{n-k}}{8k+4} - \cdots1 6 n π = k = 0 ∑ n 8 k + 1 1 6 n − k + k = n + 1 ∑ ∞ 8 k + 1 1 6 n − k − 2 k = 0 ∑ n 8 k + 4 1 6 n − k − 2 k = n + 1 ∑ ∞ 8 k + 4 1 6 n − k − ⋯
第 3 步:模运算(关键)
由于我们只关心小数部分(即十六进制位),我们可以对整数部分取模:
对于前 n nn 项,计算 16 n − k ( 8 k + 1 ) 16^{n-k} \bmod (8k+1)1 6 n − k mod ( 8 k + 1 ) 而不是 16 n − k 16^{n-k}1 6 n − k 本身,因为 模运算可以极大地减少整数大小 :
∑ k = 0 n 16 n − k ( 8 k + 1 ) 8 k + 1 (只关心小数部分) \sum_{k=0}^{n} \frac{16^{n-k} \bmod (8k+1)}{8k+1} \quad \text{(只关心小数部分)}k = 0 ∑ n 8 k + 1 1 6 n − k mod ( 8 k + 1 ) ( 只关心小数部分 )
第 4 步:二分幂模运算
使用快速幂取模算法计算 16 n − k ( 8 k + 1 ) 16^{n-k} \bmod (8k+1)1 6 n − k mod ( 8 k + 1 ) :
a b m = { 1 if b = 0 ( a b / 2 m ) 2 m if b 为偶数 ( ( a ⌊ b / 2 ⌋ m ) 2 ⋅ a ) m if b 为奇数 a^b \bmod m =
\begin{cases}
1 & \text{if } b = 0 \\
(a^{b/2} \bmod m)^2 \bmod m & \text{if } b \text{ 为偶数} \\
((a^{\lfloor b/2 \rfloor} \bmod m)^2 \cdot a) \bmod m & \text{if } b \text{ 为奇数}
\end{cases}a b mod m = ⎩ ⎨ ⎧ 1 ( a b /2 mod m ) 2 mod m (( a ⌊ b /2 ⌋ mod m ) 2 ⋅ a ) mod m if b = 0 if b 为偶数 if b 为奇数
这使得计算只需要 O ( log ( n − k ) ) O(\log(n-k))O ( log ( n − k )) 次乘法,而非 O ( n − k ) O(n-k)O ( n − k ) 次。
第 5 步:提取目标位
最终的小数部分乘以 16,整数部分就是第 n nn 位十六进制数字。
让我们计算 π \piπ 的第 2 个十六进制位(n = 2 n = 2n = 2 ,从 n = 0 n=0n = 0 开始计数,即第 0 位是整数部分 3 33 ,第 1 位是 π \piπ 的第一位十六进制小数):
手动计算验证:π = 3.243 F 6 A 8885 A 308 D 31319 8A 2 E 0 … \pi = 3.243\text{F}6\text{A}8885\text{A}308\text{D}31319\text{8}\text{A}2\text{E}0\ldotsπ = 3.243 F 6 A 8885 A 308 D 31319 8 A 2 E 0 …
第 0 位(整数部分):3
第 1 位(十六进制):2
第 2 位(十六进制):4
第 3 位(十六进制):3
我们要验证 BBP 能否直接算出第 2 位(十六进制)的 4。
π = ∑ k = 0 ∞ 1 16 k ( 4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6 ) \pi = \sum_{k=0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)π = k = 0 ∑ ∞ 1 6 k 1 ( 8 k + 1 4 − 8 k + 4 2 − 8 k + 5 1 − 8 k + 6 1 )
令 S j ( n ) = ∑ k = 0 ∞ 1 16 k ( 8 k + j ) S_j(n) = \sum_{k=0}^{\infty} \frac{1}{16^k (8k+j)}S j ( n ) = ∑ k = 0 ∞ 1 6 k ( 8 k + j ) 1 ,则:
π = 4 S 1 ( n ) − 2 S 4 ( n ) − S 5 ( n ) − S 6 ( n ) \pi = 4S_1(n) - 2S_4(n) - S_5(n) - S_6(n)π = 4 S 1 ( n ) − 2 S 4 ( n ) − S 5 ( n ) − S 6 ( n )
第 n nn 位十六进制位由 { 16 n π } \{16^n \pi\}{ 1 6 n π } (小数部分乘以 16 后的整数部分)决定。
{ 16 n S j } = { ∑ k = 0 ∞ 16 n − k 8 k + j } \{16^n S_j\} = \left\{ \sum_{k=0}^{\infty} \frac{16^{n-k}}{8k+j} \right\}{ 1 6 n S j } = { k = 0 ∑ ∞ 8 k + j 1 6 n − k }
拆分求和:
{ 16 n S j } = { ∑ k = 0 n 16 n − k 8 k + j } + { ∑ k = n + 1 ∞ 16 n − k 8 k + j } \{16^n S_j\} = \left\{ \sum_{k=0}^{n} \frac{16^{n-k}}{8k+j} \right\} + \left\{ \sum_{k=n+1}^{\infty} \frac{16^{n-k}}{8k+j} \right\}{ 1 6 n S j } = { k = 0 ∑ n 8 k + j 1 6 n − k } + { k = n + 1 ∑ ∞ 8 k + j 1 6 n − k }
第一项(前 n + 1 n+1n + 1 项):
{ 16 n S j } head = ∑ k = 0 n ( 16 n − k ( 8 k + j ) 8 k + j − 16 n − k ( 8 k + j ) 8 k + j ) \{16^n S_j\}_{\text{head}} = \sum_{k=0}^{n} \left( \frac{16^{n-k} \bmod (8k+j)}{8k+j} - \frac{16^{n-k} \bmod (8k+j)}{8k+j} \right){ 1 6 n S j } head = k = 0 ∑ n ( 8 k + j 1 6 n − k mod ( 8 k + j ) − 8 k + j 1 6 n − k mod ( 8 k + j ) )
实际上我们计算的是:
∑ k = 0 n ( 16 n − k ( 8 k + j ) ) 8 k + j \sum_{k=0}^{n} \frac{(16^{n-k} \bmod (8k+j))}{8k+j}k = 0 ∑ n 8 k + j ( 1 6 n − k mod ( 8 k + j ))
取小数部分。
第二项(剩余项)收敛很快,取少量 k kk 即可。
实际计算 n = 2 n=2n = 2 :
对于 S 1 S_1S 1 (j = 1 j=1j = 1 ):
前部(k = 0..2 k=0..2k = 0..2 ):
k = 0 k=0k = 0 : 16 2 1 = 256 1 = 0 16^{2} \bmod 1 = 256 \bmod 1 = 01 6 2 mod 1 = 256 mod 1 = 0 ,0 / 1 = 0 0/1 = 00/1 = 0
k = 1 k=1k = 1 : 16 1 9 = 16 9 = 7 16^{1} \bmod 9 = 16 \bmod 9 = 71 6 1 mod 9 = 16 mod 9 = 7 ,7 / 9 ≈ 0.777777 … 7/9 \approx 0.777777\ldots7/9 ≈ 0.777777 …
k = 2 k=2k = 2 : 16 0 17 = 1 17 = 1 16^{0} \bmod 17 = 1 \bmod 17 = 11 6 0 mod 17 = 1 mod 17 = 1 ,1 / 17 ≈ 0.0588235 … 1/17 \approx 0.0588235\ldots1/17 ≈ 0.0588235 …
后部(k = 3.. ∞ k=3..\inftyk = 3..∞ ,取少量项近似):
k = 3 k=3k = 3 : 16 − 1 / 25 = 0.0625 / 25 = 0.0025 16^{-1}/25 = 0.0625/25 = 0.00251 6 − 1 /25 = 0.0625/25 = 0.0025
k = 4 k=4k = 4 : 16 − 2 / 33 = 0.00390625 / 33 ≈ 0.00011837 16^{-2}/33 = 0.00390625/33 \approx 0.000118371 6 − 2 /33 = 0.00390625/33 ≈ 0.00011837
S 1 ≈ 0.777777 + 0.058824 + 0.0025 + 0.000118 = 0.839219 S_1 \approx 0.777777 + 0.058824 + 0.0025 + 0.000118 = 0.839219S 1 ≈ 0.777777 + 0.058824 + 0.0025 + 0.000118 = 0.839219
同样计算 S 4 S_4S 4 (j = 4 j=4j = 4 ):
k = 0 k=0k = 0 : 256 4 = 0 256 \bmod 4 = 0256 mod 4 = 0 ,0 00
k = 1 k=1k = 1 : 16 12 = 4 16 \bmod 12 = 416 mod 12 = 4 ,4 / 12 ≈ 0.333333 4/12 \approx 0.3333334/12 ≈ 0.333333
k = 2 k=2k = 2 : 1 20 = 1 1 \bmod 20 = 11 mod 20 = 1 ,1 / 20 = 0.05 1/20 = 0.051/20 = 0.05
后部趋近于 0
S 4 ≈ 0.333333 + 0.05 = 0.383333 S_4 \approx 0.333333 + 0.05 = 0.383333S 4 ≈ 0.333333 + 0.05 = 0.383333
S 5 S_5S 5 (j = 5 j=5j = 5 ):
k = 0 k=0k = 0 : 256 5 = 1 256 \bmod 5 = 1256 mod 5 = 1 ,1 / 5 = 0.2 1/5 = 0.21/5 = 0.2
k = 1 k=1k = 1 : 16 13 = 3 16 \bmod 13 = 316 mod 13 = 3 ,3 / 13 ≈ 0.230769 3/13 \approx 0.2307693/13 ≈ 0.230769
k = 2 k=2k = 2 : 1 21 = 1 1 \bmod 21 = 11 mod 21 = 1 ,1 / 21 ≈ 0.047619 1/21 \approx 0.0476191/21 ≈ 0.047619
S 5 ≈ 0.2 + 0.230769 + 0.047619 = 0.478388 S_5 \approx 0.2 + 0.230769 + 0.047619 = 0.478388S 5 ≈ 0.2 + 0.230769 + 0.047619 = 0.478388
S 6 S_6S 6 (j = 6 j=6j = 6 ):
k = 0 k=0k = 0 : 256 6 = 4 256 \bmod 6 = 4256 mod 6 = 4 ,4 / 6 ≈ 0.666667 4/6 \approx 0.6666674/6 ≈ 0.666667
k = 1 k=1k = 1 : 16 14 = 2 16 \bmod 14 = 216 mod 14 = 2 ,2 / 14 ≈ 0.142857 2/14 \approx 0.1428572/14 ≈ 0.142857
k = 2 k=2k = 2 : 1 22 = 1 1 \bmod 22 = 11 mod 22 = 1 ,1 / 22 ≈ 0.045455 1/22 \approx 0.0454551/22 ≈ 0.045455
S 6 ≈ 0.666667 + 0.142857 + 0.045455 = 0.854979 S_6 \approx 0.666667 + 0.142857 + 0.045455 = 0.854979S 6 ≈ 0.666667 + 0.142857 + 0.045455 = 0.854979
代入公式:
{ 16 2 π } = { 4 × 0.839219 − 2 × 0.383333 − 0.478388 − 0.854979 } \{16^2 \pi\} = \{4 \times 0.839219 - 2 \times 0.383333 - 0.478388 - 0.854979\}{ 1 6 2 π } = { 4 × 0.839219 − 2 × 0.383333 − 0.478388 − 0.854979 }
= { 3.356876 − 0.766666 − 0.478388 − 0.854979 } = \{3.356876 - 0.766666 - 0.478388 - 0.854979\}= { 3.356876 − 0.766666 − 0.478388 − 0.854979 }
= { 1.256843 } = 0.256843 = \{1.256843\} = 0.256843= { 1.256843 } = 0.256843
第 2 位十六进制数 = ⌊ 0.256843 × 16 ⌋ = ⌊ 4.109488 ⌋ = 4 \lfloor 0.256843 \times 16 \rfloor = \lfloor 4.109488 \rfloor = 4⌊ 0.256843 × 16 ⌋ = ⌊ 4.109488 ⌋ = 4
我们成功算出了 π \piπ 的第 2 位十六进制数是 4,而无需计算前面的位。 🎉
以下是一个完整的 BBP π \piπ 位提取实现:
def pi_hex_digit(n):
"""计算 pi 的第 n 位十六进制数字(n >= 0),n=0 是整数部分"""
from decimal import Decimal, getcontext
def mod_pow_16(exp, mod):
"""计算 16^exp mod mod 使用快速幂"""
result = 1
base = 16 % mod
while exp > 0:
if exp & 1:
result = (result * base) % mod
exp >>= 1
base = (base * base) % mod
return result
def series_term(j, n):
"""计算 S_j(n) = sum_{k=0}^{inf} 16^{n-k} / (8k+j) 的小数部分"""
s = Decimal(0)
# 前 n+1 项:使用模运算
for k in range(n + 1):
denom = 8 * k + j
num = mod_pow_16(n - k, denom)
s += Decimal(num) / Decimal(denom)
s -= int(s) # 只保留小数部分
# 后部求和(取 20 项足够)
for k in range(n + 1, n + 21):
denom = 8 * k + j
num = Decimal(16) ** (n - k)
s += num / Decimal(denom)
s -= int(s)
return s
# BBP 公式
s1 = series_term(1, n)
s4 = series_term(4, n)
s5 = series_term(5, n)
s6 = series_term(6, n)
pi_frac = (4 * s1 - 2 * s4 - s5 - s6) % 1
# 提取小数部分乘以 16
return int(pi_frac * 16)
# 验证:计算 pi 的前 20 位十六进制数字
hex_chars = "0123456789ABCDEF"
result = []
for n in range(20):
digit = pi_hex_digit(n)
result.append(hex_chars[digit])
print("π 的前 20 位十六进制数字:")
print("3." + "".join(result[1:]))
# 输出验证
expected = "243F6A8885A308D313198"
print(f"预期值: 3.{expected[1:]}")
print(f"匹配: {''.join(result[1:]).upper() == expected[1:].upper()}")
运行结果示例:
π 的前 20 位十六进制数字:
3.243F6A8885A308D31319
预期值: 3.243F6A8885A308D31319
匹配: True
阶段
复杂度
说明
模幂计算
O ( log n ) O(\log n)O ( log n )
每次二分幂取模
前部求和 (k = 0.. n k=0..nk = 0.. n )
O ( n ) O(n)O ( n )
需要计算 n + 1 n+1n + 1 次模幂
后部求和 (k = n + 1.. ∞ k=n+1..\inftyk = n + 1..∞ )
O ( 1 ) O(1)O ( 1 )
约 20 项即可收敛
总体计算第 n nn 位
O ( n log n ) O(n \log n)O ( n log n )
适用于中等 n nn 值
内存占用
O ( 1 ) O(1)O ( 1 )
仅需少量变量
算法
时间复杂度
空间复杂度
能否直接提取第 n nn 位
适用的底数
BBP 公式
O ( n log n ) O(n \log n)O ( n log n )
O ( 1 ) O(1)O ( 1 )
✅ 是
十六进制/二进制
Machin 公式
O ( n log n ) O(n \log n)O ( n log n )
O ( n ) O(n)O ( n )
❌ 否
十进制
Chudnovsky 算法
O ( n log n ) O(n \log n)O ( n log n )
O ( n ) O(n)O ( n )
❌ 否
十进制
Gauss-Legendre
O ( n log n log log n ) O(n \log n \log \log n)O ( n log n log log n )
O ( n ) O(n)O ( n )
❌ 否
任意进制
AGM 算法
O ( n log n log log n ) O(n \log n \log \log n)O ( n log n log log n )
O ( n ) O(n)O ( n )
❌ 否
任意进制
关键差异 :BBP 是唯一在常数空间下支持任意位提取的算法,Chudnovsky 和 Gauss-Legendre 计算全部 n nn 位的速度快,但不能跳过前缀。
算法
耗时
内存
位提取能力
Chudnovsky
~0.3 秒
~50 MB
❌
Machin
~2 秒
~40 MB
❌
BBP (计算全部 n nn 位)
~5 秒
~1 MB
✅
BBP (计算第 n nn 位)
~0.001 秒
~0.01 MB
✅
我们可以从积分形式出发证明 BBP 公式。
第 1 步:基本恒等式
对于 a ∈ { 0 , 1 , 2 , 3 } a \in \{0, 1, 2, 3\}a ∈ { 0 , 1 , 2 , 3 } :
∫ 0 1 / 2 x a − 1 1 − x 8 d x = ∫ 0 1 / 2 ∑ k = 0 ∞ x a − 1 + 8 k d x = ∑ k = 0 ∞ 1 2 ( a + 8 k ) / 2 ⋅ ( a + 8 k ) \int_0^{1/\sqrt{2}} \frac{x^{a-1}}{1 - x^8} dx = \int_0^{1/\sqrt{2}} \sum_{k=0}^{\infty} x^{a-1 + 8k} dx = \sum_{k=0}^{\infty} \frac{1}{2^{(a+8k)/2} \cdot (a + 8k)}∫ 0 1/ 2 1 − x 8 x a − 1 d x = ∫ 0 1/ 2 k = 0 ∑ ∞ x a − 1 + 8 k d x = k = 0 ∑ ∞ 2 ( a + 8 k ) /2 ⋅ ( a + 8 k ) 1
第 2 步:组合积分
考虑以下积分组合:
I = 4 2 ∫ 0 1 / 2 d x 1 − x 8 − 2 2 ∫ 0 1 / 2 x 3 d x 1 − x 8 − 1 2 ∫ 0 1 / 2 x 4 d x 1 − x 8 − 1 2 ∫ 0 1 / 2 x 5 d x 1 − x 8 I = \frac{4}{\sqrt{2}} \int_0^{1/\sqrt{2}} \frac{dx}{1 - x^8} - \frac{2}{\sqrt{2}} \int_0^{1/\sqrt{2}} \frac{x^3 dx}{1 - x^8} - \frac{1}{\sqrt{2}} \int_0^{1/\sqrt{2}} \frac{x^4 dx}{1 - x^8} - \frac{1}{\sqrt{2}} \int_0^{1/\sqrt{2}} \frac{x^5 dx}{1 - x^8}I = 2 4 ∫ 0 1/ 2 1 − x 8 d x − 2 2 ∫ 0 1/ 2 1 − x 8 x 3 d x − 2 1 ∫ 0 1/ 2 1 − x 8 x 4 d x − 2 1 ∫ 0 1/ 2 1 − x 8 x 5 d x
第 3 步:化简积分
引入变换 y = 2 x y = \sqrt{2}xy = 2 x ,化简后得到:
I = ∫ 0 1 4 1 + y 2 d y = π I = \int_0^1 \frac{4}{1 + y^2} dy = \piI = ∫ 0 1 1 + y 2 4 d y = π
第 4 步:展开为级数
将 1 1 − x 8 \frac{1}{1 - x^8}1 − x 8 1 展开为几何级数并积分,即可得到 BBP 公式。
BBP 公式也可以通过以下关键恒等式得到验证:
考虑部分和(N NN 项):
S N = ∑ k = 0 N 1 16 k ( 4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6 ) S_N = \sum_{k=0}^N \frac{1}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)S N = k = 0 ∑ N 1 6 k 1 ( 8 k + 1 4 − 8 k + 4 2 − 8 k + 5 1 − 8 k + 6 1 )
定义积分表示:
4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6 = ∫ 0 1 x 8 k ( 4 x 0 − 2 x 3 − x 4 − x 5 ) d x \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} = \int_0^1 x^{8k} (4x^0 - 2x^3 - x^4 - x^5) dx8 k + 1 4 − 8 k + 4 2 − 8 k + 5 1 − 8 k + 6 1 = ∫ 0 1 x 8 k ( 4 x 0 − 2 x 3 − x 4 − x 5 ) d x
代入 S N S_NS N 并与 ∑ k = 0 ∞ x 8 k 16 k = 1 1 − x 8 / 16 \sum_{k=0}^\infty \frac{x^{8k}}{16^k} = \frac{1}{1 - x^8/16}∑ k = 0 ∞ 1 6 k x 8 k = 1 − x 8 /16 1 结合可得:
lim N → ∞ S N = ∫ 0 1 4 − 2 x 3 − x 4 − x 5 1 − x 8 / 16 d x \lim_{N \to \infty} S_N = \int_0^1 \frac{4 - 2x^3 - x^4 - x^5}{1 - x^8/16} dxN → ∞ lim S N = ∫ 0 1 1 − x 8 /16 4 − 2 x 3 − x 4 − x 5 d x
经过变量替换 t = x 2 t = \frac{x}{2}t = 2 x 和部分分式分解,积分结果为 π \piπ ,证毕。
BBP 公式最重要的理论意义之一是它触发了关于正规数 (normal number)的深入研究。
定义 :一个实数是 b bb 进制正规数,当且仅当它的 b bb 进制展开中每个长度为 m mm 的数码串出现的渐进频率为 1 / b m 1/b^m1/ b m 。
如果 π \piπ 是正规数,那么它的十进制展开应该像完全随机的数字序列一样。
BBP 公式提供了研究 π \piπ 的二进制/十六进制正态性的高度非平凡工具:
研究
发现
Bailey 和 Crandall (2001)
如果某类 BBP 型常数满足某些迭代映射的均匀分布,则该常数是正规数
Bailey (2002)
数值计算验证 π \piπ 的二进制位分布统计上与随机序列一致
开放问题
π \piπ 是否正规仍然未被证明
BBP 公式是通往 π \piπ 的正规性证明的最有希望的理论工具之一。如果 π \piπ 的二进制位分布不是随机的,那么 BBP 公式的形式本身就会与这种非随机性产生明显的矛盾。
BBP 公式催生了 π \piπ 计算的分布式项目:
PiHex 项目 (1998-2000):
使用 Bablage 网络上的 25 台计算机
利用 BBP 公式的位提取特性:每台机器计算不同位置的位
不需要机器之间通信 (这是关键优势!)
结果:计算了 π \piπ 从第 10^15 位附近的约 80 位十六进制数字
与 Chudnovsky 分布式方案对比 :
特性
BBP 分布式
Chudnovsky 分布式
节点间通信
无需
需要,因为需要汇总中间结果
负载均衡
天然均衡
需要调度
容错
天然容错
节点故障需要恢复
计算效率
低(单节点慢)
高(单节点快 10-100x)
最适合
验证少量分散位
计算全部 n nn 位
任何形如以下形式的公式称为 BBP 型公式:
α = ∑ k = 0 ∞ p ( k ) b k q ( k ) \alpha = \sum_{k=0}^{\infty} \frac{p(k)}{b^k q(k)}α = k = 0 ∑ ∞ b k q ( k ) p ( k )
其中 p ( k ) p(k)p ( k ) 和 q ( k ) q(k)q ( k ) 是整数系数多项式,b bb 是 ≥ 2 \ge 2≥ 2 的整数。
PSLQ 算法(由 Ferguson 和 Bailey 提出)可以自动搜索 BBP 型恒等式:
输入 :目标常数 α \alphaα 到高精度(通常数千位)
构建 :一组 BBP 型级数的数值到同样精度
搜索 :PSLQ 寻找整数系数使得线性组合等于 α \alphaα 的数值近似
验证 :如果整数关系成立且反证误差足够小,则得到新的恒等式
已发现的 BBP 型公式数量 (截至 2024 年):
常数
BBP 型公式数量
最大底数
π \piπ
12
256
ln 2 \ln 2ln 2
8
128
π 3 \pi\sqrt{3}π 3
5
64
ζ ( 3 ) \zeta(3)ζ ( 3 )
3
32
π 2 \pi\sqrt{2}π 2
4
64
目前活跃的研究方向包括:
更高底数 :以 b = 2 m b = 2^mb = 2 m 为底,支持更快的位提取
更多常数 :将 BBP 型公式推广到 ζ \zetaζ 函数值、Catalan 常数等
正规性判定 :建立 BBP 型常数正规性的充分条件
量子算法 :利用 BBP 公式在量子计算机上提取 π \piπ 的二进制位
公式
用途
π = ∑ k = 0 ∞ 1 16 k ( 4 8 k + 1 − 2 8 k + 4 − 1 8 k + 5 − 1 8 k + 6 ) \displaystyle\pi = \sum_{k=0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)π = k = 0 ∑ ∞ 1 6 k 1 ( 8 k + 1 4 − 8 k + 4 2 − 8 k + 5 1 − 8 k + 6 1 )
BBP 标准公式
{ 16 n π } = { 4 S 1 ( n ) − 2 S 4 ( n ) − S 5 ( n ) − S 6 ( n ) } \displaystyle\{16^n \pi\} = \left\{ 4 S_1(n) - 2 S_4(n) - S_5(n) - S_6(n) \right\}{ 1 6 n π } = { 4 S 1 ( n ) − 2 S 4 ( n ) − S 5 ( n ) − S 6 ( n ) }
第 n nn 位提取
S j ( n ) = ∑ k = 0 n 16 n − k ( 8 k + j ) 8 k + j + ∑ k = n + 1 ∞ 16 n − k 8 k + j \displaystyle S_j(n) = \sum_{k=0}^{n} \frac{16^{n-k} \bmod (8k+j)}{8k+j} + \sum_{k=n+1}^{\infty} \frac{16^{n-k}}{8k+j}S j ( n ) = k = 0 ∑ n 8 k + j 1 6 n − k mod ( 8 k + j ) + k = n + 1 ∑ ∞ 8 k + j 1 6 n − k
部分和拆分
a b m = { 1 b = 0 ( a b / 2 m ) 2 m b 偶 ( ( a ⌊ b / 2 ⌋ m ) 2 ⋅ a ) m b 奇 \displaystyle a^b \bmod m = \begin{cases} 1 & b=0 \\ (a^{b/2} \bmod m)^2 \bmod m & b \text{ 偶} \\ ((a^{\lfloor b/2 \rfloor} \bmod m)^2 \cdot a) \bmod m & b \text{ 奇} \end{cases}a b mod m = ⎩ ⎨ ⎧ 1 ( a b /2 mod m ) 2 mod m (( a ⌊ b /2 ⌋ mod m ) 2 ⋅ a ) mod m b = 0 b 偶 b 奇
快速模幂
BBP 公式是 20 世纪末最令人惊讶的数学发现之一:
突破性 :首次实现在不计算前驱位的情况下提取 π \piπ 的任意十六进制位
实用性 :内存占用 O ( 1 ) O(1)O ( 1 ) ,适合分布式计算和嵌入式场景
理论价值 :为 π \piπ 的正规性证明提供了唯一的已知理论途径
可扩展性 :通过 PSLQ 算法可以系统性地发现更多 BBP 型公式
虽然对于高精度(10 9 10^91 0 9 位以上)的 π \piπ 全计算,Chudnovsky 算法更快,但在位提取 、分布式验证 和数学研究 这三个方向上,BBP 公式仍然无可替代。
Bailey, D. H., Borwein, P. B., & Plouffe, S. (1997). "On the Rapid Computation of Various Polylogarithmic Constants." Mathematics of Computation , 66(218), 903-913.
Bailey, D. H. (2000). "A compendium of BBP-type formulas for mathematical constants." Preprint , NASA Ames Research Center.
Bailey, D. H., & Crandall, R. E. (2001). "On the random character of fundamental constant expansions." Experimental Mathematics , 10(2), 175-190.
Plouffe, S. (1998). "The computation of certain numbers using a ruler and compass." Journal of Integer Sequences , 1, Article 98.1.3.
Weisstein, E. W. "BBP Formula." MathWorld -- A Wolfram Web Resource.