gcd

Q&A's, tips, howto's
Locked
eddier
Posts: 289
Joined: Mon Oct 07, 2002 2:48 pm
Location: Blue Mountain College, MS US

gcd

Post by eddier »

There is an error in the documentation in the code snippets section under Tips and Tricks.

Code: Select all

(gcd a b c ...)
gives the greatest common divisor of two or more integers. A common denominator is the

Code: Select all

(lcm a b c ...)
or least common multiple of two or more integers. The (lcm a b c ...) function could be defined as

Code: Select all

(define-macro (lcm)
  (/ (apply * (args) 2) (apply (gcd_ (args) 2)))
given the (gcd_ auxilary function.

Maybe I should have used the alternative name "gcf," greatest common factor instead of gcd.

Eddie

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Post by Lutz »

I don't get it, can you write down the whole thing? Adding 'lcm' did not work.

Lutz

eddier
Posts: 289
Joined: Mon Oct 07, 2002 2:48 pm
Location: Blue Mountain College, MS US

Post by eddier »

The documentation says gcd is a "denominator." This is not true. The gcd is the "greatest common divisor" not the "greatest common denominator." There is no greatest common denominator. For example

A common denominator for 1/4 and 1/3 could be 12. But, someone else could pick 24, and another 48, and so on.

If we want a least common denominator, it is the lcm or "least common multiple" of the two denominators.

Sorry about the error in the lcm code. The two functions should be coded as follows

Code: Select all

(define (gcd_ a b)
  # gcd auxilary function
  (let (r (% b a))
    (if (= r 0) a (gcd_ r a))))

(define-macro (gcd)
  # return the greatest common divisor of its integer arguments
  (apply gcd_ (args) 2))

(define (lcm_ a b)
  # lcm auxilary function
  (/ (* a b) (gcd_ a b)))
	
(define-macro (lcm)
  # return the least common multiple of its integer arguments
  (apply lcm_ (args) 2))

eddier
Posts: 289
Joined: Mon Oct 07, 2002 2:48 pm
Location: Blue Mountain College, MS US

Post by eddier »

Even better, leave out the lcm_ auxilary function and use a lambda.

Code: Select all

(define-macro (lcm)
  (apply (fn (x y) (/ (* x y) (gcd_ x y))) (args) 2))

Lutz
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Post by Lutz »

Thanks I will add this. At the moment I only cghanged the wording in the title.

Lutz

Locked