BBP算法所需的工作精度？

Question

我想在低内存环境中计算Pi的第n位数.因为我没有可用的小数,所以Python中这个仅整数的BBP算法是一个很好的起点.我只需要一次计算一位Pi.如何确定我可以设置的最低值D,即"工作精度的位数"？

D = 4给了我许多正确的数字,但是一些数字会被一个数字关闭.例如,计算精度为4的数字393给出了0xafda,我从中提取数字0xa.但是,正确的数字是0xb.

无论我设置多高D,似乎测试足够数量的数字会找到公式返回不正确值的数字.

当数字"接近"另一个时,我已经尝试提高精度,例如0x3fff或0x1000,但是找不到任何好的"关闭"定义; 例如,在数字计算9798给我0X Ç DE6,这是不是很接近0xd000,但正确的数字是0xd中.

任何人都可以帮我弄清楚使用这种算法计算给定数字需要多少工作精度？

谢谢,

编辑
供参考:

precision (D)   first wrong digit
-------------   ------------------
3               27
4               161
5               733
6               4329
7               21139
8+              ???

请注意,我一次计算一位数,例如:

for i in range(1,n):
    D = 3 # or whatever precision I'm testing
    digit = pi(i) # extracts most significant digit from integer-only BBP result
    if( digit != HARDCODED_PI[i] ):
        print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i]) )

Answer 1

无论我将 D 设置得有多高，似乎测试足够数量的数字都会发现公式返回错误值的数字。

如果您测试足够数量的数字，您总是会收到错误 - 该算法不使用任意精度，因此最终会出现舍入错误。

当数字不改变时，带有中断的无界迭代将很难确定给定数字位数所需的最小精度。

您最好的选择是根据经验确定它，理想情况下是通过与已知的正确源进行比较，并增加位数精度直到匹配，或者如果没有正确的源，则从最大精度开始（我猜是 14 ，因为第 15 位几乎总是包含舍入误差。）

编辑：更准确地说，该算法包括一个循环 - 从 0..n 开始，其中 n 是要计算的数字。循环的每次迭代都会引入一定量的误差。循环足够次数后，错误将侵入您正在计算的最高有效位，因此结果将是错误的。

维基百科文章使用 14 位精度，这足以正确计算 10**8 位。正如您所显示的，较少的精度位数会导致较早发生错误，因为精度较低，并且迭代次数较少，错误就会变得可见。最终结果是，随着精度位数的减少，我们可以正确计算数字的 n 值会变低。

如果精度为 D 个十六进制数字，则为 D*4 位。每次迭代时，最低有效位都会引入 0.5 位的错误，因此经过 2 次迭代，LSB 有可能出错。在求和过程中，这些误差被相加，从而累积起来。如果错误总数达到最高有效位的LSB，那么您提取的个位数将是错误的。粗略地说，就是当 N > 2**(D-0.75) 时。（纠正一些对数底数。）

根据经验推断您的数据，似乎近似拟合为 N=~(2**(2.05*D))，尽管数据点很少，因此这可能不是准确的预测变量。

您选择的 BBP 算法是迭代的，因此计算序列中的数字将花费越来越长的时间。要计算数字 0..n，将采取O(n^2)以下步骤。

维基百科文章给出了一个计算第 n 位数字的公式，不需要迭代，只需要求幂和有理数。这不会遭受与迭代算法相同的精度损失，并且您可以根据需要在恒定时间内计算 pi 的任何数字（或者最坏的对数类型，取决于模数求幂的实现），因此计算n数字可能会花费O(n)时间O(n log n)。