[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
gcd of rationals--flame added in proof
- 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 ...))
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)
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??