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

*To*: LISP-FORUM at MIT-AI*Subject*: implementation of rational numbers*From*: William A. Kornfeld <BAK at MIT-AI>*Date*: Sun ,27 Sep 81 06:39:00 EDT

The following ideas have occurred to me concerning the implementation of rational numbers. Since there is at least one (and possibly more) implementations of rational numbers happening, I'd like to have them discussed. 1. Two functions, NUMERATOR and DENOMINATOR be available that return the respective fixnums or bignums as if the rational were in lowest terms. The NUMERATOR function on an integer returns the integer and the DENOMINATOR function called on the integer returns 1. 2. There is a bit associated with each rational number that says whether or not it is known to be in lowest terms. 3. When an arithmetic operation occurs that yields a rational as a result, the resulting rational is NOT put into lowest terms [although see 5 below] 4. The functions NUMERATOR and DENOMINATOR force conversion to lowest terms (if not already there) and set the bit. 5. It is possible, for overall efficiency reasons, that if the result yields a rational where either the numerator or denominator turns out to be a bignum, a conversion to lowest terms should occur before the rational is returned (setting the bit). How these issues are handled can have important efficiency ramifications for some programs. Two other possible implementations are: (a) ALWAYS CONVERT TO LOWEST TERMS AFTER EVERY ARITHMETIC OPERATION. This would increase the time to do arithmetic operations on rationals considerably. (b) NEVER CONVERT TO LOWEST TERMS. This would make frequent calls to NUMERATOR or DENOMINATOR more expensive than necessary and, for certain programs, lead to outrageously big bignums that could have been converted to a more compact form.

- Prev by Date:
**About &parsers** - Next by Date:
**Re: fast gcd** - Previous by thread:
**About &parsers** - Next by thread:
**Re: implementation of rational numbers** - Index(es):