Nth digit of PI

[Clive Tooth]

Robert Israel wrote in message <8houlu$j9s$1 at nntp.itservices.ubc.ca>...

>[...]
>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.

Although BBP do mention that "This algorithm is, by a factor of
log(log(log(n))), asymptotically slower than the fastest known algorithms
for generating the n-th digit by generating all of the first n digits of
log(2) or pi."


>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.

An O(n^2) algorithm is described at
http://www.stud.enst.fr/~bellard/pi/pi_n2/pi_n2.html

--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document