9-1 Preliminaries

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ⁿ can be replaced by a shift right signed of n positions, and the remainder of dividing x by 2ⁿ is given by the logical and of x and 2ⁿ - 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³¹) ?(-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

Equation 1

Unsigned integer division—that is, division in which both n and d are interpreted as unsigned integers—satisfies 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—that 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).