python - BBP 算法所需的工作精度？

Question

我希望在低内存环境中计算 Pi 的第 n 位。因为我没有可用的小数，所以这个 integer-only BBP algorithm in Python一直是一个很好的起点。我一次只需要计算 Pi 的一位数。 如何确定我可以设置的最低 D，即“工作精度位数”？

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

无论我将 D 设置多高，似乎测试足够多的数字都会找到一个公式返回不正确值的数字。

当数字与另一个数字“接近”时，我尝试提高精度，例如0x3fff 或 0x1000，但找不到“关闭”的任何好的定义；例如，在数字 9798 处计算得到 0xcde6 ，它不是很接近 0xd000，但正确的数字是 0xd。

谁能帮我算出使用此算法计算给定数字需要多少工作精度？

谢谢，

编辑
供引用:

precision (D)   first wrong digit-------------   ------------------3               274               1615               7336               43297               211398+              ???

Note that I am calculating one digit at a time, e.g.:

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

No matter how high I set D, it seems that testing a sufficient number of digits finds an one where the formula returns an incorrect value.

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

当数字不改变时使用 break 的无限迭代将很难确定给定数字数量所需的最小精度。

你最好的选择是根据经验来确定它，最好是通过与已知的正确来源进行比较，并增加数字精度直到你得到匹配，或者如果没有正确的来源，从你的最大精度开始(我猜测是 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)。