BBP算法所需的工作精度？

Question

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

D = 4给了我很多正确的数字，但几个数字将会被删除一个。例如，计算数字393的精度为4给了我0xafda，从中提取数字0xa。但是，正确的数字是0xb。

无论我设置D有多高，似乎测试足够数量的数字都会找到一个公式返回错误值的位置。

我已经尝试提高精度，当数字“关闭”到另一个，例如0x3fff或0x1000，但找不到任何“关闭”的良好定义;例如，计算数字9798给我0x c 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）。