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

*To*: bak at MIT-AI, lisp-forum at MIT-AI, deutsch at PARC-Maxc, rz at MIT-MC, jlk at MIT-MC*Subject*: rational arithmetic*From*: HGBaker.Symbolics at MIT-Multics*Date*: Mon ,28 Sep 81 02:01:00 EDT

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?

- Prev by Date:
**implementation of rational numbers** - Next by Date:
**Re: Suggested new lambda-list syntax** - Previous by thread:
**Re: fast gcd** - Next by thread:
**LAMBDA syntax counter-proposal** - Index(es):