From: mpd@netcom.com (Mike Duvos)
Date: Sat, 6 Jan 1996 06:37:19 +0800
To: cypherpunks@toad.com
Subject: Pi Stuff
Message-ID: <199601052115.NAA17798@netcom17.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Various amazed people on the Pi thread wrote:

 > But BTW, isn't it interesting, that news item from a few
 > weeks ago, on an algorithm for determining individual bits
 > in Pi, regardless of whether you've calculated all the
 > previous ones.  Only problem is, it only works in
 > hexadecimal (and, obviously, binary, etc, not decimal.

 > I didn't see this result you mention, but it surprises me.

 > Yeah, well, I understand your frustration, but to me the
 > really amazing part is that the elephant flies at all, and
 > not how well he flies (<G>) (In other words, the amazing
 > thing is that there is a predictable relationship in ANY
 > base system) Chances are the thing WON'T work in base
 > 3,5,6,7,9,10,11,12,13,14,15, and any other non 2**n base.
 > Or, at least, it will take a DIFFERENT equation to work in
 > those other bases, if they work at all.

A few quick comments.  The notion that one might be able to
compute digits of Pi efficiently at any starting point in the
number is not late-breaking news.  The Chudnovsky brothers
developed a formula which permitted them to do this a number of
years ago, and used it to compute Pi to several billion digits.
Prior to that time, the Borweins' quartic interation based on
Ramanujan's modular identities and AGM techniques was the
existing state of the art.

Given a base, d, and an finite ordinal, i, the function which
computes the ith digit of the Pi in the base d is certainly a
computable one.  If we can find an algorithm for computing this
function whose time as a function of "i" does not include the
time required to compute all previous digits, then we are to a
certain extent evaluating individual digits of Pi without
calculating the previous ones.

One should keep in mind, however, that the degree to which such
things are true for algorithms lies on a continuum, with a
near-constant number of arithmetic operations at one end, and a
geometric progression at the other.  So it is not the classic
either/or situation.  Good algorithms whose times are tractable
functions of "i" are certainly desirable, and have been
discovered.

Someone suggested that radix conversion was a time-consuming
operation.  Modern FFT-based algorithms can do multiplication,
division, Nth root, reciprocal, and base conversion in
near-linear time.

Doubtless good algorithms to compute the Nth digit of Pi in any
base do exist, but their form may not be as obvious as those for
trivial bases, such as powers of two.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $