Nth digit of PI

[Robert Israel]

In article <8hogt2$57t$1 at nnrp1.deja.com>,  <david_ullrich at my-deja.com> wrote:

>    ??? In one of the references cited the authors say

>"The computation can
>be achieved without having to compute the preceeding digits. We claim
>that the algorithm has a more theoretical rather
>than practical interest, we have not found a faster algorithm, nor have
>we proven that one does not exist."

>    Regarding the "have not found a faster algorithm": Are
>you certain they're saying that none of this is any faster
>than finding the first n digits, or do they mean that they
>have not found a faster "digit-extraction" algorithm than
>the original Bailey-Borwein-Plouffe algorithm?

>    The other reference begins

>"David Bailey, Peter Borwein and Simon Plouffe have recently computed
>the ten billionth digit in the hexadecimal
> expansion of pi. They utilized an astonishing formula:

>[astonishing formula goes here]

> which enables one to calculate the dth digit of pi without being forced
>to calculate all the preceding d-1 digits."

>    If these algorithms _really_ take as much time as finding
>all the digits, as you seem to be saying, it's hard to see why
>they'd have everybody so excited (or rather why they _did_ have
>everybody so excited back when this was news). It's also hard to
>see why people would suggest that one point to the digit-extraction
>algorithms would be to be able to check the accuracy of calculations
>of _all_ the digits.

There are two different algorithms here, for two different problems.

The BBP algorithm can find a hexadecimal (or more generally, base
2^k) digit of pi, faster than any known algorithm that would find
all the digits up to this one.  This is the exciting one.

Plouffe has another algorithm that can find a digit in an arbitrary
base.  This takes C*n^3*log(n)^3 time for the n'th digit, so it is not
faster than other methods that would compute the first n digits, but it
does take very little memory.  This one has "a more theoretical rather
than practical interest".

Whether there is an algorithm for the n'th decimal digit that performs
as well as BBP is still an open question.

Robert Israel                                israel at math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2