BBP算法需要工作精度吗？

Question

我想计算 n在低内存环境中PI的数字。由于我没有小数的小数，所以 Python中的仅整数BBP算法 一直是一个很好的起点。我只需要一次计算一位PI。 如何确定我可以设置D的最低点，即“工作精度的数字数”？

d = 4给了我许多正确的数字，但是几位数字将被一个数字掉下来。例如，精度为4的计算数字393给我0xAFDA，从中提取Digit 0xa。但是，正确的数字为0xB。

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

当数字“接近”另一个，例如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]) )

Answer 1

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

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

当数字不更改时，无界的迭代将很难确定给定数量的数字所需的最低精度。

最好的选择是通过与已知的正确源进行比较，并增加数字精度，直到您获得匹配，或者如果没有正确的源，请从最大的精度开始（我猜是14，请提高数字精度的数量，并增加数字精度的数量，从而提高数字精度的数量（我猜是14） ，由于第15位数字几乎总是包含舍入错误。）

编辑：更确切地说，该算法包括一个循环 - 从0..n，其中n是要计算的数字。循环的每次迭代都会引入一定数量的错误。在循环多次之后，错误将侵占您正在计算的最重要的数字，因此结果将是错误的。

Wikipedia文章使用14位精度，这足以正确计算10 ** 8数字。如您所显示的，精度数字较少会导致较早发生错误，因为精确度和错误的迭代较少而可见。净结果是，我们可以正确计算的n值以更少的精度数字变化。

如果您有精度的十六进制数字，那就是d*4位。在每次迭代中，在最小显着的位中引入了0.5bits的误差，因此，通过2个迭代，LSB很有可能是错误的。在总结过程中，添加了这些错误，因此积累了。如果求和的数量以最重要的数字达到LSB，则提取的单位数将是错误的。粗略地说，那是n> 2 **（D-0.75）。 （正确到一些对数基础。）

从经验上推断您的数据，似乎近似拟合是n =〜（2 **（2.05*d）），尽管数据点很少，因此这可能不是准确的预测因子。

您选择的BBP算法是迭代的，因此计算序列中的数字需要逐渐更长的时间。要计算数字0..n， O(n^2) 脚步。

Wikipedia文章提供了一个计算不需要迭代，仅仅是指数和有理数的数字的公式。这不会像迭代算法一样遭受相同的精度损失，您可以根据需要在恒定时间（或最坏的对数类型，取决于使用模量实现的启动）计算PI的任何数字，因此计算 n 数字将占用 O(n) 时间可能是o（n log n）。