Re: fast gcd

[RWG@MIT-MC]

I suspect that "Lehmerizing" Brent's(?) LEFTshift binary GCD would
be even better, but, no matter what binary algorithm is used,
it is best to revert to a full multiprecision remainder step
whenever the two integers are disparate by several wordlengths,
assuming that your REMAINDER function has a faster inner loop
than your GCD.

The problem with denominator blowup is usually due to using rationals
for approximate quantities.  You should only do this if there is
something wrong with your floats, e.g. too slow, or too imprecise.

I think the main application for rationals is for precise quantities,
e.g. (loop for i from 1/2 by 1/3 to 13/6 ...) with no worry about
missing the endpoint.  Or try inverting

  1/89  1/144 1/233

  1/144 1/233 1/377

  1/233 1/377 1/610 .

You'll get denominator blowup, all right, but that's exactly what you
want.  If you float the 1/89 = .01123..., you have already lost!

MACSYMA has an extremely useful variant of gcd (which, by the way,
takes any positive number of arguments, as any good gcd (or lcm!)
should) which returns as extra values the arguments with the
gcd divided out.