gcd, lcm - greatest common divisor and least common multiple

LIBRARY

(import (rnrs))                     ;R6RS
(import (rnrs base))                ;R6RS
(import (scheme r5rs))              ;R7RS
(import (scheme base))              ;R7RS

SYNOPSIS

(gcd number ...)
(lcm number ...)

DESCRIPTION

These procedures return the greatest common divisor and the least common multiple of their arguments, respectively. The result is always non-negative. The arguments must be integers.
Greatest common divisor
If all arguments are zero, or no arguments are given, then gcd returns zero. Otherwise the greatest common divisor is the largest integer that divides each of the arguments.
Least common multiple
If there are no arguments then 1 is returned. If one of the arguments is zero then zero is returned. Otherwise lcm returns the smallest positive integer that is divisible by each of the arguments.

RETURN VALUES

Returns a non-negative number object.

EXAMPLES

(gcd 32 -36)     =>   4
(gcd)            =>   0

(lcm 32 -36)     =>   288
(lcm 32.0 -36)   =>   288.0
(lcm)            =>   1

RATIONALE

The gcd procedure is needed internally in Scheme implementations for rational number support. Its implementation is not trivial, so it makes sense to provide it to users as well. The lcm procedure is a natural complement which is easily implemented once gcd is available.

COMPATIBILITY

These procedures are identical in all RnRS revisions since R2RS. An example with an inexact number was added in R4RS, but the signature did not change.

R7RS implementations that do not support arbitrarily large exact integers will not always be able to represent the mathematically expected result of lcm.

ERRORS

These procedures can raise exceptions with the following condition types:
&assertion (R6RS)
An argument was outside its domain.
R7RS
The assertions described above are errors. Implementations may signal an error, extend the procedure's domain of definition to include such arguments, or fail catastrophically.

SEE ALSO

numerator(3scm)

STANDARDS

R4RS, IEEE Scheme, R5RS, R6RS, R7RS

HISTORY

The first Scheme report to name these procedures was R2RS. Nevertheless, Scheme has always had a gcd procedure because one was present even in MacLISP (see the LISP/MACLISP Reference Manual, 1973, Moon et al). The MacLISP version did not work with inexact numbers.

An algorithm for computing gcd appears in Euclid's Elements (circa 300 BCE).

AUTHORS

This page is part of the scheme-manpages project. It includes materials from the RnRS documents. More information can be found at https://github.com/schemedoc/manpages/.

BUGS

Ikarus Scheme 0.0.4 has the following bug: 
(gcd -1)  => -1    ; wrong! should be 1

Markup created by unroff 1.0sc,    March 04, 2023.