BBP 算法所需的工作精度？

我希望在低内存环境中计算 Pi 的第 n 位数字。由于我没有可用的小数，这Python 中的纯整数 BBP 算法 http://en.literateprograms.org/Pi_with_the_BBP_formula_%28Python%29#Using_integer_arithmetic是一个很好的起点。我一次只需要计算 Pi 的一位数。如何确定可以设置的最低“工作精度位数”D？

D=4 给出了许多正确的数字，但有几个数字会少一位。例如，以 4 的精度计算数字 393 会得到 0xafda，我从中提取数字 0xa。然而，正确的数字是0xb。

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

当数字“接近”另一个数字时，例如，我尝试提高精度0x3fff或0x1000，但找不到“关闭”的任何好的定义；例如，计算数字 9798 会得到 0xcde6 ，与 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]) )

不管我把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) steps.

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