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

*To*: lisp-forum at MIT-AI*Subject*: Re: fast gcd*From*: RWG@MIT-MC*Date*: Sat ,27 Sep 81 15:01:03 EDT

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.

- Prev by Date:
**implementation of rational numbers** - Next by Date:
**Re: implementation of rational numbers** - Previous by thread:
**implementation of rational numbers** - Next by thread:
**rational arithmetic** - Index(es):