Pi · SkyBlog

1、算法

反正切（ $arctan x$ ）

ChudnovskyChudnovsky - BS

2、计算位数

数学逻辑

在 Chudnovsky 的基础上使用 Binary splitting（一种加速各种有理项级数数值计算的技术）计算

k = 0 \sum \infty \frac{( - 1 ) ^{k} ( 6 k )! ( 13591409 + 545140134 k )}{( 3 k )! ( k ! ) ^{3} 64032 0 ^{3 k}}

现有以下一般无穷级数的模型

S (0, \infty) = \frac{a _{0} p _{0}}{b _{0} q _{0}} + \frac{a _{1} p _{0} p _{1}}{b _{1} q _{0} q _{1}} + \frac{a _{2} p _{0} p _{1} p _{2}}{b _{2} q _{0} q _{1} q _{2}} + \frac{a _{3} p _{0} p _{1} p _{2} p _{3}}{b _{3} q _{0} q _{1} q _{2} q _{3}} + \dots

该级数的部分和 $[a, b)$

S (a, b) = \frac{a _{a} p _{a}}{b _{a} q _{a}} + \frac{a _{a + 1} p _{a} p _{a + 1}}{b _{a + 1} q _{a} q _{a + 1}} + \frac{a _{a + 2} p _{a} p _{a + 1} p _{a + 2}}{b _{a + 2} q _{a} q _{a + 1} q _{a + 2}} + \dots + \frac{a _{b - 1} p _{a} p _{a + 1} p _{a + 2} \dots p _{b - 1}}{b _{b - 1} q _{a} q _{a + 1} \dots p _{b - 1}}

定义一些额外的函数

P (a, b) Q (a, b) B (a, b) T (a, b) = p_{a} p_{a + 1} \dots p_{b - 1} = q_{a} q_{a + 1} \dots q_{b - 1} = b_{a} b_{a + 1} \dots b_{b - 1} = B (a, b) Q (a, b) S (a, b)

则存在以下关系
$P (a, a + 1) Q (a, a + 1) B (a, a + 1) S (a, a + 1) T (a, a + 1) = p_{a} = q_{a} = b_{a} = \frac{a _{a} p _{a}}{b _{a} q _{a}} = B (a, a + 1) Q (a, a + 1) S (a, a + 1) = b_{a} q_{a} \frac{a _{a} p _{a}}{b _{a} q _{a}} = a_{a} p_{a}$
若 $a <= m <= b$ 则
$P (a, b) Q (a, b) B (a, b) T (a, b) = P (a, m) P (m, b) = Q (a, m) Q (m, b) = B (a, m) B (m, b) = B (m, b) Q (m, b) T (a, m) + B (a, m) P (a, m) T (m, b)$
- 其中 $T (a, b)$ 的证明
  $T (a, b) = B (m, b) Q (m, b) T (a, m) + B (a, m) P (a, m) T (m, b) = B (m, b) Q (m, b) B (a, m) Q (a, m) S (a, m) + B (a, m) P (a, m) B (m, b) Q (m, b) S (m, b) = B (a, b) Q (a, b) S (a, m) + B (a, b) P (a, m) Q (m, b) S (m, b) = B (a, b) (Q (a, b) S (a, m) + \frac{P ( a , m ) Q ( a , b )}{Q ( a , m )} S (m, b)) = B (a, b) Q (a, b) (\frac{a _{a} p _{a}}{b _{a} q _{a}} + \frac{a _{a + 1} p _{a} p _{a + 1}}{b _{a + 1} q _{a} q _{a + 1}} + \frac{a _{a + 2} p _{a} p _{a + 1} p _{a + 2}}{b _{a + 2} q _{a} q _{a + 1} q _{a + 2}} + \dots + \frac{a _{m - 1} p _{a} p _{a + 1} p _{a + 2} \dots p _{m - 1}}{b _{m - 1} q _{a} q _{a + 1} \dots p _{m - 1}} + \frac{p _{a} p _{a + 1} \dots p _{m - 1}}{q _{a} q _{a + 1} \dots q _{m - 1}} \cdot (\frac{a _{m} p _{m}}{b _{m} q _{m}} + \frac{a _{m + 1} p _{m} p _{m + 1}}{b _{m + 1} q _{m} q _{m + 1}} + \frac{a _{m + 2} p _{m} p _{m + 1} p _{m + 2}}{b _{m + 2} q _{m} q _{m + 1} q _{m + 2}} + \dots + \frac{a _{b - 1} p _{m} p _{m + 1} p _{m + 2} \dots p _{b - 1}}{b _{b - 1} q _{m} q _{m + 1} \dots p _{b - 1}})) = B (a, b) Q (a, b) (\frac{a _{a} p _{a}}{b _{a} q _{a}} + \frac{a _{a + 1} p _{a} p _{a + 1}}{b _{a + 1} q _{a} q _{a + 1}} + \frac{a _{a + 2} p _{a} p _{a + 1} p _{a + 2}}{b _{a + 2} q _{a} q _{a + 1} q _{a + 2}} + \dots + \frac{a _{m - 1} p _{a} p _{a + 1} p _{a + 2} \dots p _{m - 1}}{b _{m - 1} q _{a} q _{a + 1} \dots p _{m - 1}} + \frac{p _{a} p _{a + 1} \dots p _{m - 1}}{q _{a} q _{a + 1} \dots q _{m - 1}} + \frac{a _{m} p _{a} p _{a + 1} \dots p _{m}}{b _{m} q _{a} q _{a + 1} \dots q _{m}} + \frac{a _{m + 1} p _{a} p _{a + 1} \dots p _{m + 1}}{b _{m + 1} q _{a} q _{a + 1} \dots q _{m + 1}} + \frac{a _{m + 2} p _{a} p _{a + 1} \dots p _{m + 2}}{b _{m + 2} q _{a} q _{a + 1} \dots q _{m + 2}} + \dots + \frac{a _{b - 1} p _{a} p _{a + 1} \dots p _{b - 1}}{b _{b - 1} q _{a} q _{a + 1} \dots p _ b - 1}) = B (a, b) Q (a, b) S (a, b) = T (a, b)$

现在我们计算 $S (0, n)$ ，可以按照如下方式二分迭代计算（ $m = ⌊ \frac{0 + n}{2} ⌋$ ）。这样在计算结束时只进行一次除法，这会大大加快计算速度，因为除法比乘法慢。

S (0, n) = \frac{T ( 0 , n )}{B ( 0 , n ) Q ( 0 , n )} = \frac{B ( m , n ) Q ( m , n ) T ( 0 , m ) + B ( 0 , m ) P ( 0 , m ) T ( m , n )}{B ( 0 , m ) B ( m , n ) \cdot Q ( 0 , m ) Q ( m , n )} = \dots

回到我们待计算的级数上，忽略待计算级数 $(- 1)^{k}$ 项，则存在以下对应关系（之前的递推关系 $\frac{A _{k}}{A _{k - 1}} = \frac{p _{k}}{q _{k}}$ ）

a_{k} b_{k} p_{0} q_{0} p_{k} q_{k} = 13591409 + 545140134 k = 1 = 1 = 1 = (6 k - 5) (2 k - 1) (6 k - 1) = \frac{k ^{3} \cdot 64032 0 ^{3}}{24}

https://pi-calculator.netlify.app/https://www.craig-wood.com/nick/articles/pi-chudnovsky/