Required accuracy for the BBP algorithm?

Question

I want to calculate the digit n th Pi in a low memory environment. Since I don't have decimals, this integer BBP algorithm in Python has been a great starting point. I only need to calculate one Pi digit at a time. How can I determine the lowest that I can set D, the "number of working precision digits"?

D = 4 gives me many correct digits, but several digits will be disabled by one. For example, calculating the 393 digit with an accuracy of 4 gives me 0xafda, from which I extract the digit 0xa. However, the correct digit is 0xb.

No matter how tall I set D, it seems like testing enough numbers finds one where the formula returns the wrong value.

I tried to increase accuracy when the figure is "close" to another, for example. 0x3fff or 0x1000, but cannot find a good definition of "close"; for example, calculating on the number 9798 gives me 0x c de6, which is not very close to 0xd000, but the correct digit is 0xd.

Can someone help me figure out what working accuracy is needed to compute a given figure using this algorithm?

Thanks,

<i> change>
For reference:

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

Note that I calculate one digit at a time, for example:

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 like testing enough numbers finds one where the formula returns the wrong value.

You will always get an error if you test a sufficient number of digits - the algorithm does not use arbitrary accuracy, so rounding errors will ultimately be displayed.

Unlimited iteration with a gap, when the digit does not change, it will be difficult to determine the minimum accuracy required for a given number of digits.

It is best to determine it empirically, ideally, by comparing with a known correct source and increasing the number of digits until you get a match, or if the correct source is not available, start with maximum accuracy (which I guess is 14, since the 15th the figure almost always contains a rounding error.)

EDIT: more precisely, the algorithm includes a cycle - from 0..n, where n is the number to calculate. Each iteration of the loop will result in some error. After looping a sufficient number of times, the error will encroach on the most significant digit that you calculate, and therefore the result will be incorrect.

The wikipedia article uses 14 digits of accuracy, and this is enough to correctly calculate the number 10 ** 8. As you have shown, fewer digits lead to errors that occur earlier, because there is less accuracy, and the error becomes visible with fewer iterations . The end result is that the value for n, for which we can correctly calculate the digit, becomes lower with fewer digits.

If you have D hexadecimal digits of precision, then D * 4 bits. An error of 0.5 bits is introduced with each iteration in the smallest bit value, therefore, with 2 iterations, the probability that the LSB is erroneous. During the summation, these errors are added and accumulated. If the number of total errors reaches the least significant digit in the most significant digit, then the one digit you choose will be incorrect. Roughly speaking, this is when N> 2 ** (D-0.75). (Correct some logarithmic base.)

Empirically extrapolating your data, it seems that the approximate match is N = ~ (2 ** (2.05 * D)), although there is some data, so this may not be an accurate predictor.

The BBP algorithm you have chosen is iterative, so it takes a longer time to calculate the numbers in the sequence. To calculate the numbers 0..n, follow steps O(n^2) .

The Wikipedia article provides a formula for calculating the nth digit, which does not require iteration, just raising to a power and rational numbers. This will not lead to the same loss of accuracy as the iterative algorithm, and you can calculate any digit pi as needed in constant time (or, in the worst case, the logarithmic type, depending on the implementation of exponentiation with a module), so computing n digits will take O(n) time, possibly O (n log n).