implementation of rational numbers

[William A. Kornfeld <BAK at MIT-AI>]

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.