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

*To*: Bill Gosper <rwg at SPA-NIMBUS>*Subject*: Irrational GCD*From*: Alan Bawden <ALAN at SCRC-TENEX>*Date*: Sat, 05 Jan 1985 08:19:00 -0000*Cc*: BUG-LISPM at SWW-WHITE, common-lisp at SU-AI, DCP at SCRC-QUABBIN, numerics at SPA-NIMBUS

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.

- Prev by Date:
**re: Yellow pages** - Next by Date:
**Silicon Valley Syndrome** - Previous by thread:
**Irrational GCD** - Next by thread:
**Silicon Valley Syndrome** - Index(es):