Nth digit of PI
Clive Tooth
clive at pisquaredoversix.force9.co.uk
Fri Jun 9 06:38:10 EDT 2000
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
More information about the Python-list
mailing list