Nth digit of PI

[Clive Tooth]

Russell Wallace wrote:

> Clive Tooth wrote:
> >
> > Russell Wallace wrote in message <394889C3.1ED5 at esatclear.ie>...
> > >Correct me if I'm wrong, but I thought memory was the limiting factor?
> > >i.e. that a good algorithm on typical hardware can fill all the
> > >available memory with digits of pi in a few days or so?
> >
> > You are wrong. The discussion was about methods of calculating digit N of pi
> > (in some base) without computing digits 1 thru N-1 . This can be done in
> > about O(log(N)) bits of memory.
> 
> Yes, that's what I mean.  The O(log N) memory consumption would, it
> seems to me, make it possible to reach far higher values of N than if
> you had to calculate digits 1 thru N-1, even if the amount of
> computation required isn't much different.

A calculation of the Nth digit of pi, where the limit was the amount of
_memory_ available, say 100MB on some typical PC, would mean an
extremely large N and a truly stupendous amount of time. Greater than
the age of the universe, etc.

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