SRFI 141: Integer division

This SRFI is currently in *final* status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to `srfi-141@nospamsrfi.schemers.org`

. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

- Received: 2016/8/29
- 60-day deadline: 2016/10/28
- Draft #1 published: 2016/8/29
- Draft #2 published: 2016/9/22
- Draft #3 published: 2016/12/1
- Finalized: 2016/12/14

This SRFI provides a fairly complete set of integral division and remainder operators.

None at present.

Most programming languages provide at least one operation for division,
and sometimes related operations for computing integral quotients and
remainders. (There is at least one (fortunately today defunct)
programming language that provides addition, subtraction, and division,
with multiplication notably absent, being expressible as division.)
Everyone agrees that a pair of operators for computing integral
quotients *q* and remainders *r* from the division of
a numerator (dividend) *n* by a denominator (divisor) *d*,
should satisfy the relations

*n*=*dq*+*r*,- |
*r*| < |*d*|, and *q*is an integer.

Such a pair of operators will be called a division operator pair. Many programming languages provide only one division operator pair. Some, such as C, leave the semantics unspecified when either or each of the numerator and the denominator is negative. If the numerator and denominator are both integers, then the remainder will also be an integer.

To describe the semantics of a division operator pair, it suffices to
define the integer *q*, from which *r* can be uniquely
derived by the relation

r=n-dq,

provided that this choice of *q* induced an *r*
satisfying |*r*| < |*d*|. For an extensive
discussion of five of the six division operator pairs proposed
here, and some broken but standardized operator pairs that fail
to satisfy properties (1)-(3), see Raymond T. Boute,
"The Euclidean Definition of the Functions DIV and MOD", ACM TOPLAS
14(2), April 1992, pp. 127-144.

Unfortunately, most programming languages give nondescript names such as DIV(IDE), QUOT(IENT), MOD(ULO), and REM(AINDER) to these operations. The language should make clear to programmers what division operations their programs are performing, especially when negative numerators and denominators can arise, but perhaps may not often be tested.

The R5RS gives the names `quotient` and `remainder` to the truncating
division operator pair, and the name `modulo` to the remainder half of
the flooring division operator pair. For all these three procedures in
the R5RS, the numerator may be any integer, and the denominator may be any
nonzero integer.

The R6RS gives the names `div`, `mod`, and `div-and-mod` to the Euclidean division operator
family, and the names `div0`, `mod0`, and `div0-and-mod0` to the balanced operator family.
For all six of these procedures, the numerator may be
any real number, and the denominator may be any nonzero real number. The R5RS procedures
are also available in the R5RS compatibility library.

The truncate and floor families are part of R7RS-small. Three of them are also available under their R5RS names, for backward compatibility. The numerator may be any integer, and the denominator may be any nonzero integer.

Common Lisp provides four integral division functions, `floor`, `ceiling`,
`truncate`, and `round`; and two remainder functions, `mod` and `rem`. The
division functions comprise both the quotient and remainder of a
division operator pair, and return them as two values, of which the
latter, the remainder, may be implicitly ignored in Common Lisp. The
denominator argument is optional in Common Lisp's integral division
functions; if omitted, it is taken to be 1. `mod` is the remainder half
of the flooring division operator pair; `rem` is the remainder half of
the truncating division operator pair. Common Lisp does not provide
any part of the Euclidean division operator pair.

For all six of these functions in Common Lisp, the numerator may be any
real number, and the denominator may be any nonzero real number. Common
Lisp also provides four extra functions `ffloor`, `fceiling`, `ftruncate`,
and `fround`, which differ from their `f`-less variants only in
floating-point contagion rules.

For each of six division operator pairs — floor, ceiling, truncate,
round, Euclidean and balanced — there is a family of three procedures: one, named
`<operator>/`, to compute the division and to return both quotient and
remainder as multiple return values; one, named `<operator>-quotient`,
to return only the quotient; and one, named `<operator>-remainder`, to
return only the remainder. Each division operator pair is specified by
defining the quotient *q* in terms of the numerator *a* and the denominator *n*.
Tacitly the remainder *r* is as above: *r* = *n* - *dq*.

It is an error if any of the arguments are not integers (exact or inexact). It is also an error to supply zero as a denominator to any of these procedures. If any argument is inexact, the result is inexact, unless the implementation can prove that the inexactness cannot affect the result, as in the case of dividing an exact zero by an inexact number.

`(floor/ `*numerator* *denominator*`)`

`(floor-quotient `*numerator* *denominator*`)`

`(floor-remainder `*numerator* *denominator*`)`

q= floor(n/d)

Thus *r* is negative iff *d* is negative.

`(ceiling/ `*numerator* *denominator*`)`

`(ceiling-quotient `*numerator* *denominator*`)`

`(ceiling-remainder `*numerator* *denominator*`)`

q= ceiling(n/d)

Thus *r* is negative iff *d* is non-negative.

If *denominator* is the number of units in a block, and <numerator> is
some number of units, then `(ceiling-quotient `*numerator* *denominator*`)`
gives the number of blocks needed to cover *numerator* units. For
example, *denominator* might be the number of bytes in a disk sector, and
*numerator* the number of bytes in a file; then the quotient is the
number of disk sectors needed to store the contents of the file. For
another example, *denominator* might be the number of octets in the
output of a cryptographic hash function, and *numerator* the number of
octets desired in a key for a symmetric cipher, to be derived using
the cryptographic hash function; then the quotient is the number of
hash values needed to concatenate to make a key.

`(truncate/ `*numerator* *denominator*`)`

`(truncate-quotient `*numerator* *denominator*`)`

`(truncate-remainder `*numerator* *denominator*`)`

q= truncate(n/d)

Thus *r* is negative iff *n* is negative. However, by any non-unit denominator, the
quotient of +1, 0, or -1 is 0; that is, three contiguous numerators by
a common denominator share a common quotient. Of the other division
operator pairs, only the round pair exhibits this property.

`(round/ `*numerator* *denominator*`)`

`(round-quotient `*numerator* *denominator*`)`

`(round-remainder `*numerator* *denominator*`)`

q= round(n/d)

The round function rounds to the nearest integer,
breaking ties by choosing the nearest even integer.
Nothing general can be said about the sign of *r*. Like the truncate
operator pair, the quotient of +1, 0, or -1 by any non-unit denominator is 0, so
that three contiguous numerators by a common denominator share a common
quotient.

`(euclidean/ `*numerator* *denominator*`)`

`(euclidean-quotient `*numerator* *denominator*`)`

`(euclidean-remainder `*numerator* *denominator*`)`

If

d> 0,q= floor(n/d); ifd< 0,q= ceiling(n/d).

This division operator pair satisfies the stronger property

0 <=

r< |d|,

used often in mathematics. Thus, for example,
`(euclidean-remainder `*numerator* *denominator*`)`
is always a valid index into a vector whose
length is at least the absolute value of *denominator*.
This division operator pair is so
named because it is the subject of the Euclidean division algorithm.

`(balanced/ `*numerator* *denominator*`)`

`(balanced-quotient `*numerator* *denominator*`)`

`(balanced-remainder `*numerator* *denominator*`)`

This division operator pair satisfies the property

-|

d/2| <=r< |d/2|.

When *d* is a power of 2, say 2^{k} for some *k*, this reduces to

-2

^{(k - 1)}<=r< 2^{(k - 1)}.

Computer scientists will immediately recognize this as the interval of
integers representable in two's-complement with *k* bits.

The implementation is in the repository of this SRFI, and includes the following files:

`srfi-141-impl.scm`

- The R5RS-based implementation`srfi-141.scm`

- Chicken library`srfi-141.sld`

- R7RS library

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Arthur A. Gleckler