Re: Closer and closer you move to the Cantorian cliff

From: Michel Hack (hack_at_watson.ibm.com)
Date: 03/24/05 

Date: 24 Mar 2005 08:20:57 -0800

tinyurl.com/uh3t wrote:
>
http://groups.google.co.in/groups?selm=1105863295.677791.34430%40z14g2000cwz.googlegroups.com

[snipped various TM definitions of computable numbers, which are
basically ok]
>
> Note also that there is no known way to generate the nth digit of pi
> without in fact generating all or most of the earlier digits at the
> same time, or at least generating all the information necessary to
> generate those earlier digits. In fact usually the calculations are
> done in binary in the first place, generating all or most of the bits
> in an approximation to pi, then that approximation is used to
generate
> the decimal digits corresponding to it. If you really only want a
> single digit, I suppose you could generate the binary approximation
and
> then use a finite-state modular algorithm to directly generate just
the
> single desired digit without actually generating all the earlier
> digits.

You need to catch up with new developments in the last 10 years.
Google for BBP algorithm (Bailey, Borwein and Plouffe) which generates
the nth hexadecimal digit (hence, trivially, binary digit) of Pi (and
other "polylogarithmic" transcendental numbers) directly and
efficiently, without having to compute all preceding bits. This method
has been used to compute the trillionth bit or so of Pi, whereas Pi's
full expansion has "only" been explored up to 50 billion digits or so
(by Prof. Kanada, in Japan).

More recently, Plouffe found a similar way to compute the nth decimal
digit of Pi also. This method is actually less efficient (in terms of
computation time) than the best traditional methods (which compute all
preceding digits), but it does have the advantage that it needs very
little space to hold intermediary results (unlike traditional methods
where the entire sequence of digits has to be available at some point).

Michel.

Relevant Pages

  • Re: An Anti-Cantorian Paradox
    ... to ..., the nth digit of the nth list number is "1" if n is odd, and is ... Cantorian set theory a diagonal number cannot be a member of the list ... digits instead of single digits, counting off digits by twos to the ... This number is different at the nth pair of binary digits from the nth ...
    (sci.math)
  • Re: Closer and closer you move to the Cantorian cliff
    ... > Note also that there is no known way to generate the nth digit of pi ... > generate those earlier digits. ... > in an approximation to pi, then that approximation is used to ... computation time) than the best traditional methods (which compute all ...
    (sci.logic)
  • Re: Closer and closer you move to the Cantorian cliff
    ... > Note also that there is no known way to generate the nth digit of pi ... > generate those earlier digits. ... > in an approximation to pi, then that approximation is used to ... computation time) than the best traditional methods (which compute all ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... >> Let me first reorder the list to simplify, ... It is clear that the nth number on the list needs no more than n digits ... Any number in WM's list has a finite position, say nth, in that list, so ...
    (sci.math)
  • Re: Excellent accuracy in the HP50G GAMMA function--how do they do it?
    ... Stirling's approximation, truncated at the fourth or fifth term, is ... digits accuracy (in a calculating environment that allows for several ... more guard digits). ... the code internall that keeps roundoff error down to size so it is ...
    (comp.sys.hp48)