# 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: 410

Hello,

I'm looking to compute the *n*th 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 0x**c**de6 , 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