[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[RZ at MC: Rational and complex numbers]
- To: common-lisp@SU-AI
- Subject: [RZ at MC: Rational and complex numbers]
- From: David A. Moon <Moon%SCRC-TENEX%MIT-MC@SU-DSN>
- Date: Thu, 23 Jun 1983 21:51:00 -0000
- Cc: rz%MIT-MC@SU-DSN
Here's a clarification from Rich Zippel of his feelings about rational
and complex numbers. I am simply forwarding this to the group for
informational purposes; I am not advocating doing anything about it
at this time. My feeling is that he is talking at a much higher level
than the Common Lisp language deals with. A system for modeling
general rings, fields, and other algebras would be a valuable thing to
have, but has little to do with the implementation of ordinary arithmetic in Lisp
except that the ordinary numbers would be a subset of the data types in
which the algebra system would deal. Then we must address the question
of whether rational numbers are valuable enough in their own right (rather than
as one particular algebra) that they belong in the language. The impression
I get is that a number of people have felt that they would far rather use
rational numbers than floating-point numbers for certain kinds of computations
(e.g. IC layout).
Date: Wed, 22 Jun 1983 18:08:00 -0000
From: Richard E. Zippel <RZ at MIT-MC>
Subject: Rational and complex numbers
To: Carl W. Hoffman <CWH at SCRC-TENEX>
Cc: Moon at SCRC-TENEX, rz at mit-mc
Your second message on this topic completed what you said in your first
message. I think you should have sent them both together. Were you really
trying to say that the design of rationals as proposed for Common Lisp should
not be used, or that better designs were possible? Why don't you make an
What I was trying to say, was that the current design of rationals in Common
Lisp is inadequate and not sufficiently visionary. I personally think that
not having a rational number system in Common Lisp is better than having one
which will have to be removed at some later date when we understand the
problem more fully. In particular I am afraid that we won't produce a new
system, or will resist the introduction of such a system because of the
investment that had been made in the current system.
Making a good alternate proposal is a major research undertaking. Let
me mention some of the issues and some ideas that should be pursued.
You are trying to allow users to use algebraic structures based on the
integers. There are three issues here:
(1) Creation of algrebaic types
(2) The gathering together of the appropriate algorithms/code for
different types created by the user
(3) A theory of coercion.
(1) Creation of algebraic types:
There are several mechanisms that might be used to create new
structures. The following list some of the most important that should be
provided by the system.
(a) quotient structures: This is how rational numbers are constructed.
The numerators and denominators need not come from the same domain, but
the denominators must be a subset of the numerators. This allows you to
deal with localization, farey sequenced and other mathematical
(b) Polynomials: You might think that adding algebraic numbers would be
the next construction mechanism, but it is best to build it on top of
polynomials. The coefficients must be the elements of some algebraic
structure, the exponents are integers.
(c) Modular structures. Some domain, were an element different from
zero is now assumed to be zero. E.g., integers mod 5, gaussian
integers. The guassian integers are polyonomials in X where we have
assumed X^2 + 1 is zero. This allows more complex structures like
(d) Matrices, vector spaces, etc.
With these constructors most interesting mathematic data structures can
(2) Getting the code together.
Now that you can build arbitrarily complex structures you are faced with the
problem of making sure the right algorithm is associated with a
particular operation. This is one of the purposes of the Capsule paper.
It describes some mechanisms that allow the creation of an algebraic
structure to control the particular algorithms that are used for
operations like plus and times. I could go into more detail here later
if its interesting.
Coercion is the process of make semantic identification of an abstract
mathematical object. Let describe what I've been calling a
``computational structure'' which is one way to deal with some of the
problems of coercion. Computational structures consist of a set of
domains which are in use (Z and Q are examples, there may be several Z's
and Q's), and maps between the these domains. There may be more than
one map between two domains. Certain of these maps are labeled as being
canonical maps. When an operation like (+ A B) occurs, the following
things happen: If A and B come from the same domain, then the +
operation of that domain is used (that's the easy case, and the only one
I believe should be implemented in Common Lisp now). If A and B are of
different domains, then these two domains are located in the
computational structure, and the canonical maps are followed to find a
domain in which both elements can be considered. These elements are
coerced into this new domain using the canonical maps, and the the
operation is executed in the new domain. Notice that the new domain
need not be the domain of A or B but can be a third domain.
There are a lot of complications with the scheme just described, but
some variation of it is probably OK.
This should give you some idea the issues I'm worried about. [For Dave:
Carl and I have spoken about this to some length already, so he can
probably fill in many of the details.]
It seems to me that you are asking for ways to represent 3*pi, 3*sqrt(2),
etc., and, when divided by 4, have these yield (3/4)*pi, (3/4)*sqrt(2), etc.
I would say that this has more to do with representing all of R (or with
representing extensions of Z) than with the injections of Z into Q.
Even if no changes are made to the current design (which is what I expect will
happen), don't you feel that the advantages of having simple-minded rationals
available in Common Lisp will outweigh the disadvantages? You don't have to
use them if you don't want to.
If you think this is clear enough and worth saving you might want to
forward this to Common-Lisp.