gcd of rationals--flame added in proof

[Bill Gosper <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??