Rational and complex numbers

[Richard E. Zippel <RZ @ MIT-MC>]

This message is not intended to change any of the decisions that have been
made in common lisp but to place into the record some comments on numbers
that I hope will prove useful next time.  The thrust of these comments are
that the addition of these new data types to common lisp is premature---we
still don't understand the issues of coercion and type extension well enough
to define these particular types.

What are the types trying to represent?

One of the reasons that bignums are so important in Lisp that it allows us to
deal with a mathematically reasonable and well defined domain, namely the
rational integers as opposed to an ad hoc set of quantities: the bit
patterns that fit into a word.

In defining new data types for Lisp it should be clear what mathematical
domain we are trying to represent with the new type.  Floating point numbers
are an attempt to represent the real numbers, but of course they are not a
particulary good representation.  IEEE arithmetic, with gradual underflow is
better (quantities larger than the exponent range can be represented by
infinities, and small numbers gradually lose precision as they get closer to
0), but a bigfloat representation (with bignum exponents) provides an even
better model of the reals.

Common Lisp rational numbers are an attempt to model the quotient field of
the rational integers: Q.  All elements of Q have distinct representations
as common lisp rational numbers which is good.  Now what does 1 mean?  Is it
an element of Z or Q?  Here the problem is that we aren't sure, it depends
on what else it is combined with.  We are trying to make 1 serve double duty
as multiplicative identity of both Z and Q, two very distinct rings.  Of
course there are injections of Z into Q, and even a canonical one which we
can use when we accidentally combine an element of Z with one of Q, but
there cases when other injections are more appropriate.  It seems more
natural to me, when writing programs, to make the coercion be more explicit.
This is somewhat reminescent of the problems we once had when namelists and
namestrings and pathnames could all be used interchangably.

Considering the complex types, mixed complex seems a little silly from this
point of view.  Algebraically its not really a terribly interesting
structure.  Either you are trying to represent the complex numbers (C) or
not.  Mixing makes the internal coercions much more complicated and the
resulting mathematical structures has almost as many peculiarities as
fixnums.  If you complexes are trying to represent C, then the two
components should represent R as well as possible, integers, rational
numbers and the like don't.  

The gaussian number (complexes with integers coefficients) are interesting,
but why were they singled out?  This is just one of a large number of
different algebraic extensions of the integers.  Numbers of the form
a+b*sqrt(7) are just as useful as numbers of the form a+b*sqrt(-1).  The
same holds for complexes with rational coefficients.  Of course, higher
degree algebraic numbers are also reasonable candidates, as are polynomials
and rational functions, matrices ...

Fundamentally, my comment is that new data types have been introduced to
common lisp, and we don't yet have a good model of what they are trying to
represent and what the coercion mechanisms are to be between them.


For those who don't know me, I am one of the people who helped develop
Macsyma where we spent and are spending a great deal of time struggling with
these very issues.