computation with exact real numbers by continued fractions

[Kragen Sitaker]

Computers can easily represent small integers exactly, and with a bit
more effort, they can represent arbitrary-sized integers exactly.
Computations done with integers generally have no error to worry about.

With a little more effort, computers can represent any rational number
exactly.

But we compute frequently with irrational numbers.  In particular,
distances between points are usually irrational.

In HAKMEM items 97-101, available at
<URL:http://24.1.71.186/ChezInwap/pdp10/hbaker/hakmem/cf.html> among
other places, Bill Gosper talks about doing exact numerical
computations with regular continued fractions.  These have the
advantage that they can represent a considerably larger domain of
numbers exactly.  With the methods Gosper discusses, in fact, it
appears that you can "represent" any real number as a continued
fraction, as long as you can write a program to emit the terms of the
number.  Gosper claims that there are no small programs to do this for
common transcendental functions, but I haven't really read the whole
item.

<URL:http://www.cecm.sfu.ca/publications/organic/confrac/node8.html>
says that "The continued fraction for \pi is not known, in the sense
that no pattern has been identified.  There are many open questions
about this continued fraction --- for example, it is not known if the
elements of the continued fraction are bounded."  This is dated June
1995.

(Related: <URL:http://www.isr.umd.edu/~jasonp/pi-ref.txt> talks about
different people computing numerical values for \pi, including Bill
Gosper, who was the first to compute 17 million digits of it, using a
continued fraction discovered by Ramanujan.  Its bibliography says,
"Gosper, Bill: private communications; Very brief discussion of his
continued fraction method.")

There appears to be some of Gosper's arithmetic stuff implemented in C
at <URL:http://perso.club-internet.fr/fbalsalo/>.

There's an introduction to continued fractions at
<URL:http://www.astro.virginia.edu/~eww6n/math/ContinuedFraction.html>.
It also mentions another algorithm by Gosper for computing with
continued fractions.

There is a rumor I've seen elsewhere that Gosper writes papers on
computing with continued fractions and distributes them to people he
knows.  The remarks in this paper tend to confirm that.

Gosper now works at Macsyma.com; perhaps these papers contain trade
secrets he does not want to disclose.  That conjecture makes me feel
like I'm living in the Dark Ages.

<URL:http://www.astro.virginia.edu/~eww6n/books/ContinuedFractions.html>
is a bibliography on continued fractions.  One entry says, "Gosper,
R.W.  Continued Fraction Arithmetic.  Preprint."

<URL:http://www.cco.caltech.edu/~ilan/publications.html> is a set of
"online pubilcations" which includes an "efficient implementation of
Gosper's continued fraction arithmetic", presumably for Mathematica.

<URL:http://www.mathsoft.com/asolve/constant/khntchn/khntchn.html> has
some interesting, but unrelated stuff about Khintchine's constant,
roughly 2.685452001.  It and some nearby pages have links to some
interesting email from Bill Gosper, such as
<URL:http://www.mathsoft.com/asolve/constant/itrexp/gosper.html>.

Another approach (?) is being (more recently, like last year) pursued
by a Dr. Peter Potts at Imperial College.  See, for example,
<URL:http://theory.doc.ic.ac.uk:80/~pjp/> and the documents linked
therefrom.

His PhD thesis, finished last year, is on exact real arithmetic using
something called "Mobius Transformations".  I don't know if his methods
are extensible to operations other than arithmetic, although I can't
imagine why anyone would care about them if they weren't.  (Arithmetic
can be done nicely with rational numbers, and the only normal way to
get nonrational numbers is through non-arithmetic functions on rational
numbers.)

He says that Gosper used 2-dimensional Moebius transformations in the
HAKMEM item, and describes what that means, at
<URL:http://theory.doc.ic.ac.uk/~pjp/ieee/node7.html>.

-- 
<kragen@pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
Computers are the tools of the devil. It is as simple as that. There is no
monotheism strong enough that it cannot be shaken by Unix or any Microsoft
product. The devil is real. He lives inside C programs. -- philg@mit.edu