rational arithmetic

[HGBaker.Symbolics at MIT-Multics]

I don't know the details of the current implementations of bignums
or rationals on either the Lispm or Smalltalk-80.  However, both groups
might check Knuth Vol. II regarding rational arithmetic implementations,
as it has some good suggestions.
1.  GCD of large integers can be "approximated" with single precision
calculations (see Alg. L), thus reducing the cost of this operation.
Single precision doesn't have to be full word if you don't want.

GCD can also be speeded up recursively using this hack, I believe.
2.  Producing fractions which are in lowest terms is often easier if
you know that all inputs are already in lowest terms (very much
like normalization!).  You don't necessarily have to do a complete
GCD at the end.
3.  GCD of smaller numbers is easier than GCD of larger numbers because
GCD is O(n^2), for usual implementations.  Therefore, several small
GCD's can take less time than one large one.
4.  GCD is 1 for randomly chosen numbers 61 percent of the time.  Therefore,
special casing is important.
5.  rational operations tend to blow up like crazy, so one's first
impression is to throw up one's hands and not do GCD's at all.  However,
people tend to do rational problems that have simple answers, in which
case keeping lowest terms helps a lot.
6.  My intuition tells me that you don't want to put off GCD'ing more
than once (i.e. do it every other operation), else you waste more time
multiplying, CONSing and garbage collecting than you do GCD'ing.
7.  GCD should be able to be highly optimized in the microcode, at least
for the single precision stuff, and so it is probably worth doing the
GCD if it keeps the numbers single precision.
8.  What is the Macsyma experience with rationals?  Or do they treat them
as expressions of integers and go through the standard simplifier?