SRFI 141: Integer division
This SRFI provides a fairly complete set of integral division and remainder operators.
SRFI Description
This page is primarily intended to document the forms exported by the egg. See the SRFI document for a more comprehensive description.
Specification
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.
Procedure families
Floor
[procedure] (floor/ numerator denominator)[procedure] (floor-quotient numerator denominator)
[procedure] (floor-remainder numerator denominator)
Satisfies
q = floor(n/d)
Thus r is negative iff d is negative.
Ceiling
[procedure] (ceiling/ numerator denominator)[procedure] (ceiling-quotient numerator denominator)
[procedure] (ceiling-remainder numerator denominator)
Satisfies
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
[procedure] (truncate/ numerator denominator)[procedure] (truncate-quotient numerator denominator)
[procedure] (truncate-remainder numerator denominator)
Satisfies
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
[procedure] (round/ numerator denominator)[procedure] (round-quotient numerator denominator)
[procedure] (round-remainder numerator denominator)
Satisfies
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
[procedure] (euclidean/ numerator denominator)[procedure] (euclidean-quotient numerator denominator)
[procedure] (euclidean-remainder numerator denominator)
If d > 0, q = floor(n/d); if d < 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
[procedure] (balanced/ numerator denominator)[procedure] (balanced-quotient numerator denominator)
[procedure] (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.
Exceptions
This egg tries to give useful information when things go wrong. Procedure arguments are type-checked; when a type check fails, a condition of kind (exn type assertion) is raised. Division by zero is signaled by raising an (exn arithmetic) condition. This conforms to the condition protocol used by CHICKEN's internal libraries.
See the Module (chicken condition) page for more information.
About this egg
Dependencies
The test egg is needed to run the included tests.
Authors
SRFI 141 and the implementation used by this egg were created by Taylor Campbell and John Cowan.
Maintainer
Wolfgang Corcoran-Mathe
wcm at sigwinch dot xyzzy without the zy
Repository
Version history
- 0.1
- Packaged for Chicken Scheme 5 (Sergey Goldgaber)
- 0.2
- (2022-04-25) New maintainer, add types, use available (chicken base) forms.
- 0.2.1
- (2022-09-01) Add type and divisor checks, minimal tests.
- 1.0.0
- (2022-09-01) Stable public API. (Yes, it was stable from the start.) Register srfi-141 feature.
License
Copyright (C) Taylor Campbell, John Cowan (2016). All Rights Reserved.
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.