Nth digit of PI

[Peter Schneider-Kamp]

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

I think the point is, that it is faster if you just desire ONE digit,
but if you want to calculate all the digits up to a certain limit you
are a bit slower than with a standard algorithm.

just-guessing-from-my-reading-ly y'rs Peter
--
Peter Schneider-Kamp          ++47-7388-7331
Herman Krags veg 51-11        mailto:peter at schneider-kamp.de
N-7050 Trondheim              http://schneider-kamp.de