[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*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 alternate proposal? 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 structures. (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 algebraic functions. (d) Matrices, vector spaces, etc. With these constructors most interesting mathematic data structures can be built. (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. (3) Coercion 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.

- Prev by Date:
**Re: Memberp** - Next by Date:
**[RZ at MC: Rational and complex numbers]** - Previous by thread:
**My poll of Lisp users** - Next by thread:
**[RZ at MC: Rational and complex numbers]** - Index(es):