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

*To*: ALAN@SCRC-STONY-BROOK.ARPA, fateman%ucbdali@UCB-VAX.ARPA*Subject*: gcd of rationals--flame added in proof*From*: Bill Gosper <rwg@RUSSIAN.SPA.Symbolics.COM>*Date*: Wed, 20 Feb 85 01:50 PST*Cc*: rem@MIT-MC.ARPA, numerics@SCRC-STONY-BROOK.ARPA, common-lisp@SU-AI.ARPA*In-reply-to*: <850129023720.8.RWG@RUSSIAN.SPA.Symbolics.COM>

Date: Tue, 29 Jan 85 02:37 PST From: Bill Gosper <rwg@RUSSIAN.SPA.Symbolics.COM> Date: Saturday, 19 January 1985 01:03-EST From: Alan Bawden <ALAN at SCRC-TENEX> Date: Friday, 28 December 1984, 01:28-PST From: Bill Gosper <rwg at SPA-NIMBUS> Date: Wednesday, 19 December 1984, 23:45-EST From: David C. Plummer in disguise <DCP at SCRC-QUABBIN> [(GCD 1\4 1\3) errs.] . . . BTW, the correct answer is 1\12. Not as far as ZL is concerned. Nor CL for that matter. Ouch! They must have been jet-lagged at those CL meetings. As Schroeppel pointed out several millenia back, (GCD A\B C\D) = (GCD A C)/(LCM B D), assuming args are in lowest terms. MACSYMA has long known this. You know Gosper, I had always assumed that people who proposed to extend GCD to the rationals were just confused about just what GCD really was, so I was quite surprised to hear that this was an idea endorsed by Schroeppel. So I thought about it for a while... In what sense must the GCD of 1/3 and 1/4 be 1/12? Suppose I pick some subring of Q that contains both 1/3 and 1/4 and I look at the ideal generated by 1/3 and 1/4. Certainly that ideal is the same as the ideal generated by 1/12, and in general the formula you give above will always yeild such a generator, but there are many other elements in the ring that generate that ideal. In fact, since 1/12 is a unit in any subring of Q, that ideal must be generated by 1, so why not say GCD(1/3,1/4)=1? What is the additional constraint you impose that requires 1/12? Well, suppose that instead of thinking about GCD as defined in terms of generators of ideals in subrings of Q, we think about GCD as defined in terms of generators of Z-modules contained in Q. In that case, the formula above gives the unique (modulo sign) generator of the module generated by the arguments to GCD. But that seems somewhat arbitrary; suppose I was working with some ring other than Z, call it A, and I wanted to play with A-modules contained in Q? No problem! Although the formula can't always give you a unique generator, it will give you -one- of the generators, which is certainly the best you can ask for. Summary: I'm convinced. This really is the right way to extend GCD to the rational numbers if you are going to do it at all. (Since my suggestions that GCD, NUMERATOR and DENOMINATOR be extended in the -only- possible way to the complex integers were ignored, I have little hope that Common Lisp will adopt the idea, however.) But the absoLULU is further down page 202 of the CL book: "Mathematically, (lcm) should return infinity." This is so wildly absurd that I can't even guess the fallacy that led to it. It should simply be 1. It is clearly a result of taking the identity (LCM ...) = (/ (ABS (* ...)) (GCD ...)) too seriously. Hell, that's only valid for exactly TWO arguments! (+ A B) is (+ (MAX A B) (MIN A B)), but (+ A B C) isn't (+ (MAX A B C) (MIN A B C)) and (+ A) isn't (+ (MAX A) (MIN A)) ! From: fateman@ucbdali (Richard Fateman) To: rwg@NIMBUS.SPA.Symbolics Subject: Re: Irrational GCD The notion of a GCD over fractions is probably not such a great thing to put in as a primitive in a programming language. I guess it shows how advanced Common Lisp is.. The usual kind of programming language has trouble with REMAINDER. It was a real pain to get straight in macsyma, as I recall. If you worry about unique factorization domains, I believe fields (e.g. rational numbers) don't qualify for the GCD operation. Which means you can probably extend the operation any way you please so long as it coincides on the integers... e.g. gcd (a\b,c\d) == if b=d=1 then gcd(a,c) else 1. Barf, what is all this prissy pedantry? Groups, modules, rings, ufds, patent- office algebra. Barf! GCD once stood for Greatest Common Divisor, an English Phrase. What is the greatest rational that produces and integer when you divide it into 1/3 and 1/4? Answer: 1/12. Another view. Extend unique prime factorization to rationals. Then you got p1^a1 p2^a2 . . . just like with integers, except now the ai can be negative. GCD is still prod pi^min(ai of each arg), and LCM is still max. Even (DEFUN EGCD (A B) (IF (ZEROP B) (ABS A) (EGCD B (\ A B)))) does the right thing with rationals! Then you can (DEFUN ELCM (&REST NUMS) (CL:// (APPLY #'EGCD (MAPCAR #'CL:// NUMS)))), i.e., reciprocate the GCD of the reciprocals. (Like MIN is negative of MAX of negatives.) Why isn't there a CL destructive MAP on sequences??

**Follow-Ups**:**gcd of rationals--flame added in proof***From:*Guy Steele <godot!gls@AQUINAS>

- Prev by Date:
**doc strings** - Next by Date:
**gcd of rationals--flame added in proof** - Previous by thread:
**doc strings** - Next by thread:
**gcd of rationals--flame added in proof** - Index(es):