John says:
> [...]
> However, it isn't true that computers cannot handle real numbers.
> There have been several papers on exact real arithmetic (I believe
> by Corky Cartwright and David Lester). The idea is to use lazy
> representations of unbounded data structures, such as continued
> fractions, to represent a real number. Just as it's possible for a
> finite computer to perform certain computations on infinite graphs,
> it's also possible for it to perform certain computations on real
> numbers. (Naturally, there are some computations that will fail to
> terminate.)
Thanks John. I really must get around to the final final revision of
the paper on continued fractions and Haskell that must be the longest
delayed paper ever submitted to JFP.
> I'm not sure what the current state of this research is, but we
> should look into it. There may be serious limitations on what you
> can do with exact real numbers in a computer, but some useful
> applications have been reported. Of course you can't print all the
> digits of a real number, or ask for its least significant digit, but
> you can add them, or print them to any desired accuracy.
There are limitations to what can be done, but they are familiar to
all of us: _continuity_is_important_.
That is, methods such as signum which are not continuous in their
arguments, are not implementable.
So far I have shown that it is possible to factor arbitrary monic
polynomials (constructively!) and hence we can find eigenvalues. The
associated unit eigenvectors are not continous for repeated
eigenvalues of 0, and hence we can't do that. Edalat and Escardo have
shown that continuity (in the arithmetic sense) is the same as
continuity in the Scott topology sense we are all familiar with.
> The Floating types should be called Floating, and the name Real
> should be reserved for numbers that actually obey the algebraic laws
> for real numbers.
Amen.
> Here's a good project for Haskell 2: study the literature on exact
> real arithmetic, and figure out whether the technology is effective
> enough so that Haskell 2 should have a Real type. Of course it
> should also have the Floating types, and most people will use Float
> (rather than Real) just as most people use Int (rather than
> Integer). However, it would be wonderful if Haskell 2 could have
> Integer, Rational and Real types which satisfy the corresponding
> algebraic laws.
I have put up two files so far:
ftp://ftp.cs.man.ac.uk/pub/man-fp/arithmetic/cauchy.tar.gz
ftp://ftp.cs.man.ac.uk/pub/man-fp/arithmetic/rationals.tar.gz
The first is an implementation of the computable reals (in Haskel 1.2)
using higher order functions to represent the computable reals.
The second is an alternative implementation of the rationals using
continued fractions. Why you might ask? Well just try using
Newton-Raphson naively to find a well-defined single root of a
quartic; e.g.
solve x^4 - 2 = 0 starting at x_0 = 2.
What's the problem with the value of x_{20}?
> There need to be several flavors of complex numbers, since there are
> two orthogonal issues: (1) how to represent the complex itself
> (real+imaginary, polar representation etc.), and (2) what underlying
> type is used for the components (Float, Double, Rational, Real etc.)
The polar representation is not computable (consider the continuity of
the phase for a representation of 0).
---
David Lester.
ps I'll put up the other implementations and papers next week sometime,
but I must make a trip to London, as my mother is in intensive care.
Aplogies.
pps It's nice to talk arithmetic to FPer's rather than FP to the arithmetic
community.
