Nth digit of PI

[Clive Tooth]

Kent wrote:

> Clive Tooth <clive at pisquaredoversix.force9.co.uk> wrote in message
> news:8hqhhi$396$1 at mail.pl.unisys.com...
> > 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."
> 
> I'm not getting this. It's "faster than any known algorithm that would find
> all the digits up to this one", but it's "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". How can it be both faster and asymptotically slower? Does
> this mean "faster for small enough values of n, but slower for large enough
> values"? If so, about how big are "small enough" and "large enough"?

David Bailey, Peter Borwein and Simon Plouffe talk about this half way
down page 8 of "On the Rapid Computation of Various Polylogarithmic
Constants" (or half way down page 670 of "Pi: A Source Book").

Their algorithm requires that arithmetic (in particular, multiplication)
be done with a precision of O(log(n)) digits. Calculating all the digits
of pi requires doing arithmetic with a precision of O(n) digits.
Depending on the hardware capabilities of the computer, and the value of
n, it is quite possible that multiplication with a precision of
O(log(n)) digits is just the "ordinary" hardware multiplication. In this
case the BBP algorithm will be faster than than any known algorithm that
would find all the digits up to n.

For huge values of n, where we might be using Strassen-Schönhage
multiplication, even to attain a precision of O(log(n)) digits, then
computing _all_ the digits would be (just) faster.

As to what is "small enough" and what is "large enough" this would
depend on the capabilities of the hardware and the details of the
programming of the algorithms. I would guess that n being "a few
million" would be small enough for any likely hardware and likely
programming.

Note that the _memory_ requirements for the two methods are vastly
different. About O(n) bits for all n digits, and about O(log(n)) bits
for just the nth digit.

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