Required Working Precision for the BBP Algorithm?

Posted by brainfsck on Stack Overflow See other posts from Stack Overflow or by brainfsck
Published on 2010-05-24T05:15:50Z Indexed on 2010/05/24 5:21 UTC
Read the original article Hit count: 353

Filed under:


I'm looking to compute the nth digit of Pi in a low-memory environment. As I don't have decimals available to me, this integer-only BBP algorithm in Python has been a great starting point. I only need to calculate one digit of Pi at a time. How can I determine the lowest I can set D, the "number of digits of working precision"?

D=4 gives me many correct digits, but a few digits will be off by one. For example, computing digit 393 with precision of 4 gives me 0xafda, from which I extract the digit 0xa. However, the correct digit is 0xb.

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.

I've tried upping the precision when the digit is "close" to another, e.g. 0x3fff or 0x1000, but cannot find any good definition of "close"; for instance, calculating at digit 9798 gives me 0xcde6 , which is not very close to 0xd000, but the correct digit is 0xd.

Can anyone help me figure out how much working precision is needed to calculate a given digit using this algorithm?

Thank you,

© Stack Overflow or respective owner

Related posts about python

Related posts about algorithm