This chapter and the following one give a
number of tricks and algorithms involving "computer division" of
integers. In mathematical formulas we use the expression x/y to denote
ordinary rational division, x ?y to denote signed computer division of integers
(truncating toward 0), and to denote unsigned computer division of integers. Within C code, `x/y` of course
denotes computer division, unsigned if either operand is unsigned, and signed
if both operands are signed.

Division is a complex process, and the algorithms involving it are often not very elegant. It is even a matter of judgment as to just how signed integer division should be defined. Most high-level languages and most computer instruction sets define the result to be the rational result truncated toward 0. This and two other possibilities are illustrated below.

`牋牋牋牋牋牋?truncating牋?modulus牋牋?floor `

`7?牋牋牋 =牋?2 rem 1牋牋?2 rem 1牋牋?2 rem 1 `

`(-7)?牋?=牋 -2 rem -1牋?-3 rem 2牋牋 -3 rem 2 `

`7?-3)牋?=牋 -2 rem 1牋牋 -2 rem 1牋牋 -3 rem -2 `

`(-7)?-3) =牋?2 rem -1牋牋 3 rem 2牋牋?2 rem -1 `

The relation dividend
= quotient * divisor + remainder holds for all three possibilities. We
define "modulus" division by requiring that the remainder be
nonnegative. ^{[1]}
We define "floor" division by requiring that the quotient be the
"floor" of the rational result. For positive divisors, modulus and
floor division are equivalent. A fourth possibility, seldom used, rounds the
quotient to the nearest integer.

^{[1]} I know I will be taken to task for this nomenclature, because there
is no universal agreement that "modulus" implies
"nonnegative." Knuth's "mod" operator [Knu1] is the
remainder of floor division, which is negative (or 0) if the divisor is
negative. Several programming languages use "mod" for the remainder
of truncating division. However, in mathematics "modulus" is
sometimes used for the magnitude of a comple x number (nonnegative), and in
congruence theory the modulus is generally assumed to be positive.

One advantage of modulus and floor division
is that most of the tricks simplify. For example, division by 2^{n} can be replaced by a shift right signed of n
positions, and the remainder of dividing x by 2^{n} is given by the logical and of x and 2^{n} - 1. I suspect that modulus and floor division
more often give the result you want. For example, suppose you are writing a
program to graph an integer-valued function, and the values range from imin to imax. You
want to set up the extremes of the ordinate to be the smallest multiples of 10
that include imin and imax.
Then the extreme values are simply (imin ?10)
* 10 and ((imax + 9) ?10) * 10 if modulus or
floor division is used. If conventional division is used, you must evaluate
something like:

if (imin >= 0) gmin = (imin/10)*10;

else牋牋 牋牋牋gmin = ((imin - 9)/10)*10;

`if (imax >= 0) gmax = ((imax + 9)/10)*10; `

`else牋牋牋牋牋 gmax = (imax/10)*10; `

Besides the quotient being more useful with modulus or floor division than with truncating division, we speculate that the nonnegative remainder is probably wanted more often than a remainder that can be negative.

It is hard to choose between modulus and
floor division, because they differ only when the divisor is negative, which is
unusual. Appealing to existing highlevel languages does not help, because they
almost universally use truncating division for `x/y` when the operands are
signed integers. A few give floating-point numbers, or rational numbers, for
the result. Looking at remainders, there is confusion. In Fortran 90, the `MOD` function
gives the remainder of truncating division and `MODULO` gives the
remainder of floor division (which can be negative). Similarly, in Common Lisp
and ADA, REM is the remainder of truncating division, and MOD is the remainder
of floor division. In PL/I, `MOD` is always nonnegative (it is the remainder of modulus division). In
Pascal, `A` `mod` `B` is defined only for `B` > 0, and then it is the nonnegative
value (the remainder of either modulus or floor division).

Anyway, we cannot change the world even if we
knew how we wanted to change it, ^{[2]}
so in what follows we will use the usual definition (truncating) for x ?y.

^{[2]} Some do try. IBM's PL.8 language uses modulus division, and Knuth's
MMIX machine's division instruction uses floor division [MMIX].

A nice property of truncating division is that it satisfies

However, care must be exercised when applying
this to transform programs, because if n or d is the maximum negative number, -n or -d cannot be
represented in 32 bits. The operation (-2^{31}) ?(-1) is an overflow
(the result cannot be expressed as a signed quantity in two's-complement notation),
and on most machines the result is undefined or the operation is suppressed.

Signed integer (truncating) division is related to ordinary rational division by

Unsigned integer division梩hat is, division in which both n and d are interpreted as unsigned integers梥atisfies the upper portion of (1).

In the discussion that follows, we make use of the following elementary properties of arithmetic, which we don't prove here. See [Knu1] and [GKP] for interesting discussions of the floor and ceiling functions.

Theorem D1. For x real, k an integer,

Theorem D2. For n, d integers, d > 0,

If d < 0:

Theorem D3. For x real, d an integer 0:

Corollary. For a, b real, b 0, d an integer 0,

Theorem D4. For n, d integers, d 0, and x real,

In the theorems below, rem(n, d) denotes the remainder of n divided by d. For negative d, it is defined by rem(n, -d) = rem(n, d), as in truncating and modulus division. We do not use rem(n, d) with n < 0. Thus, for our use, the remainder is always nonnegative.

Theorem D5. For n 0, d 0,

(whichever value is greater than or equal to 0 and less than |d|).

Theorem D6. For n 0, d 0,

Theorems D5 and D6 are easily proved from the basic definition of remainder梩hat is, that for some integer q it satisfies

provided n 0 and d 0 (n and d can be non-integers, but we will use these theorems only for integers).