Notes on integer division.
Version of Thursday 24 March 2016.
Dave Barber's other pages.

§ 1. Important in mathematics is the elementary operation known as division, which is often introduced in elementary schools.

It requires two numerical inputs. The first is called a numerator or dividend; and the second a denominator or divisor. In nearly all contexts, including this report, the denominator is not allowed to be zero. Division generates either one or two outputs, depending on what sort of numbers are used.

There will be one output (the quotient) when using for instance rational numbers or real numbers. This variety of division was created in order to be the inverse of multiplication, in the sense that multiplying the quotient by the denominator yields the numerator exactly.

There will be two outputs (the quotient and remainder) when using for example ordinary integers or Gaussian integers. With inputs of an integral nature, it is not always possible to find a quotient such that the quotient times the denominator equals the numerator exactly. Instead is sought an approximate quotient, with the remainder to house the error. More specifically, when the remainder is added to the product of the quotient and the dividend, the numerator is obtained (see Euclidean division). This report is an examination of what the word "approximate" might mean.

Remember that the quotient in one-output division is always exact, but the quotient in two-output division might not be.


In the text below, majuscules N will stand for numerator, D denominator, Q quotient, and R remainder. Ordered-pair notation with square brackets will be used to write the results of the prototypical division problem: N ÷ D = [ Q, R ].

Sometimes it is helpful to have a functional notation for the quotient or remainder. Hence define the quo function as a way of extracting the quotient from the ordered pair, established by the identity N ÷ D = [ quo (N, D), R ]. Similarly define function rem such that N ÷ D = [ Q, rem (N, D) ].

In nearly every treatment of integer division, including what follows, these two key constraints are enforced:

Q × D + R = N
| R | < | D |

where the vertical lines indicate absolute value.


When the integers involved in division are limited to nonnegative values, there is no question what the results ought to be. For instance, 37 ÷ 5 = [ 7, 2 ]. If a larger Q were chosen, then R < 0; if Q were smaller, then | R | ≥ | D |.

However, when all four values are allowed to be negative, options emerge. All of the following satisfy the two key constraints:

+37 ÷ +5 = [ +7, +2 ]or +37 ÷ +5 = [ +8, −3 ]
+37 ÷ −5 = [ −7, +2 ]or +37 ÷ −5 = [ −8, −3 ]
−37 ÷ +5 = [ −7, −2 ]or −37 ÷ +5 = [ −8, +3 ]
−37 ÷ −5 = [ +7, −2 ]or −37 ÷ −5 = [ +8, +3 ]

On the other hand, if N is a multiple of D, then R = 0, and the answer must be unique:

+63 ÷ +7 = [ +9, 0 ]
+63 ÷ −7 = [ −9, 0 ]
−63 ÷ +7 = [ −9, 0 ]
−63 ÷ −7 = [ +9, 0 ]

When R ≠ 0, and there is a choice of two answers, is one better than the other? Many programming languages support integer division, but they offer minimal guidance on this question as they are remarkably inconsistent when dealing with negative values. Meanwhile, mathematical number theory gives little enlightenment as it rarely investigates integer division involving negative numbers.

To aid in organizating this matter, division problems can be split into cases according to N and D:

The final four cases will be called quadrants, and are the focus of this report. In nearly every programming language that offers integer division of negatives, there is within each quadrant a consistent rounding policy, and it is one or the other of the following:

Within a language, however, knowing the rounding policy within one quadrant gives little clue how other quadrants will be rounded; and consistency between languages is notoriously lacking. With four quadrants, and two standard rounding schemes, 16 = 24 possibilities arise, and it helps to list them in table one below wherein:

A division rule is modular if and only if N ÷ D = [ Q, R ] implies (N + D) ÷ D = [ Q + 1, R ] for all N and all nonzero D. Modularity, or the lack of it, is most conspicuous when N < 0 but N + D > 0, or vice versa.

table one
including examples
quadrant 1
N < 0, D < 0
quadrant 2
N < 0, D > 0
quadrant 3
N > 0, D < 0
quadrant 4
N > 0, D > 0
characterization line
number
Q → −∞
−37 ÷ −5 = [ +7, −2 ]
Q → −∞
−37 ÷ +5 = [ −8, +3 ]
Q → −∞
+37 ÷ −5 = [ −8, −3 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
Q → −∞ always R × D ≥ 0 modular 1
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
  2
Q → +∞
+37 ÷ −5 = [ −7, +2 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
  3
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
Q → −∞ when N < 0
Q → +∞ when N > 0
R × Q ≤ 0   4
Q → +∞
−37 ÷ +5 = [ −7, −2 ]
Q → −∞
+37 ÷ −5 = [ −8, −3 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
  5
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
Q → −∞ when D < 0
Q → +∞ when D > 0
R ≤ 0 modular 6
Q → +∞
+37 ÷ −5 = [ −7, +2 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
Q → 0 always R × N ≥ 0   7
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
  8
Q → +∞
−37 ÷ −5 = [ +8, +3 ]
Q → −∞
−37 ÷ +5 = [ −8, +3 ]
Q → −∞
+37 ÷ −5 = [ −8, −3 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
  9
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
Q ← 0 always R × N ≤ 0   10
Q → +∞
+37 ÷ −5 = [ −7, +2 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
Q → +∞ when D < 0
Q → −∞ when D > 0
R ≥ 0 modular 11
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
  12
Q → +∞
−37 ÷ +5 = [ −7, −2 ]
Q → −∞
+37 ÷ −5 = [ −8, −3 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
Q → +∞ when N < 0
Q → −∞ when N > 0
R × Q ≥ 0   13
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
  14
Q → +∞
+37 ÷ −5 = [ −7, +2 ]
Q → −∞
+37 ÷ +5 = [ +7, +2 ]
  15
Q → +∞
+37 ÷ +5 = [ +8, −3 ]
Q → +∞ always R × D ≤ 0 modular 16
in every case, N × D × Q ≥ 0    

Not obvious from table one is that rounding based on zero satisfies certain equalities:

+ quo (−N, −D) = − quo (−N, +D) = − quo (+N, −D) = + quo (+N, +D)
and
+ rem (−N, −D) = + rem (−N, +D) = − rem (+N, −D) = − rem (+N, +D)
when
Q is consistently rounded toward zero (line 7)
or
Q is consistently rounded away from zero (line 10)

For eight of the sixteen policies, no concise characterization is apparent. With each, there is one direction of infinity rounding that differs from the other three, and one direction of zero rounding that differs from the other three. As a result, these eight policies are less likely to be useful than the other eight. In table two below, the exceptions are marked with diamonds:

table two
quadrant 1
N < 0, D < 0
quadrant 2
N < 0, D > 0
quadrant 3
N > 0, D < 0
quadrant 4
N > 0, D > 0
line
number
Q → −∞
Q → 0
Q → −∞
Q ← 0
Q → −∞
Q ← 0
Q → +∞
Q ← 0
2
Q → −∞
Q → 0
Q → −∞
Q ← 0
Q → +∞
Q → 0
Q → −∞
Q → 0
3
Q → −∞
Q → 0
Q → +∞
Q → 0
Q → −∞
Q ← 0
Q → −∞
Q → 0
5
Q → −∞
Q → 0
Q → +∞
Q → 0
Q → +∞
Q → 0
Q → +∞
Q ← 0
8
Q → +∞
Q ← 0
Q → −∞
Q ← 0
Q → −∞
Q ← 0
Q → −∞
Q → 0
9
Q → +∞
Q ← 0
Q → −∞
Q ← 0
Q → +∞
Q → 0
Q → +∞
Q ← 0
12
Q → +∞
Q ← 0
Q → +∞
Q → 0
Q → −∞
Q ← 0
Q → +∞
Q ← 0
14
Q → +∞
Q ← 0
Q → +∞
Q → 0
Q → +∞
Q → 0
Q → −∞
Q → 0
15


An alternative to the system above is to round Q so as to minimize the absolute value of R. When D is an odd number, this procedure is unambiguous:

−36 ÷ −5 = [ +7, −1 ]
−37 ÷ −5 = [ +7, −2 ]
−38 ÷ −5 = [ +8, +2 ]
−39 ÷ −5 = [ +8, +1 ]
−36 ÷ +5 = [ −7, −1 ]
−37 ÷ +5 = [ −7, −2 ]
−38 ÷ +5 = [ −8, +2 ]
−39 ÷ +5 = [ −8, +1 ]
+36 ÷ −5 = [ −7, +1 ]
+37 ÷ −5 = [ −7, +2 ]
+38 ÷ −5 = [ −8, −2 ]
+39 ÷ −5 = [ −8, −1 ]
+36 ÷ +5 = [ +7, +1 ]
+37 ÷ +5 = [ +7, +2 ]
+38 ÷ +5 = [ +8, −2 ]
+39 ÷ +5 = [ +8, −1 ]

On the other hand, when D is even, there is a choice:

−51 ÷ −6 = [ +8, −3 ]or −51 ÷ −6 = [ +9, +3 ]
−51 ÷ +6 = [ −8, −3 ]or −51 ÷ +6 = [ −9, +3 ]
+51 ÷ −6 = [ −8, +3 ]or +51 ÷ −6 = [ −9, −3 ]
+51 ÷ +6 = [ +8, +3 ]or +51 ÷ +6 = [ +9, −3 ]

One way to resolve this is to choose, in the halfway case, one of the sixteen options in the table above. Another way is to round so that the quotient will be an even number; the sequences in table three below illustrate how to do this; highlighted are the halfway cases:

table three
quadrant 1
N < 0, D < 0
quadrant 2
N < 0, D > 0
quadrant 3
N > 0, D < 0
quadrant 4
N > 0, D > 0
−42 ÷ −6 = [ +7,  0 ]
−43 ÷ −6 = [ +7, −1 ]
−44 ÷ −6 = [ +7, −2 ]
−45 ÷ −6 = [ +8, +3 ]
−46 ÷ −6 = [ +8, +2 ]
−47 ÷ −6 = [ +8, +1 ]
−48 ÷ −6 = [ +8,  0 ]
−49 ÷ −6 = [ +8, −1 ]
−50 ÷ −6 = [ +8, −2 ]
−51 ÷ −6 = [ +8, −3 ]
−52 ÷ −6 = [ +9, +2 ]
−53 ÷ −6 = [ +9, +1 ]
−54 ÷ −6 = [ +9,  0 ]
−42 ÷ +6 = [ −7,  0 ]
−43 ÷ +6 = [ −7, −1 ]
−44 ÷ +6 = [ −7, −2 ]
−45 ÷ +6 = [ −8, +3 ]
−46 ÷ +6 = [ −8, +2 ]
−47 ÷ +6 = [ −8, +1 ]
−48 ÷ +6 = [ −8,  0 ]
−49 ÷ +6 = [ −8, −1 ]
−50 ÷ +6 = [ −8, −2 ]
−51 ÷ +6 = [ −8, −3 ]
−52 ÷ +6 = [ −9, +2 ]
−53 ÷ +6 = [ −9, +1 ]
−54 ÷ +6 = [ −9,  0 ]
+42 ÷ −6 = [ −7,  0 ]
+43 ÷ −6 = [ −7, +1 ]
+44 ÷ −6 = [ −7, +2 ]
+45 ÷ −6 = [ −8, −3 ]
+46 ÷ −6 = [ −8, −2 ]
+47 ÷ −6 = [ −8, −1 ]
+48 ÷ −6 = [ −8,  0 ]
+49 ÷ −6 = [ −8, +1 ]
+50 ÷ −6 = [ −8, +2 ]
+51 ÷ −6 = [ −8, +3 ]
+52 ÷ −6 = [ −9, −2 ]
+53 ÷ −6 = [ −9, −1 ]
+54 ÷ −6 = [ −9,  0 ]
+42 ÷ +6 = [ +7,  0 ]
+43 ÷ +6 = [ +7, +1 ]
+44 ÷ +6 = [ +7, +2 ]
+45 ÷ +6 = [ +8, −3 ]
+46 ÷ +6 = [ +8, −2 ]
+47 ÷ +6 = [ +8, −1 ]
+48 ÷ +6 = [ +8,  0 ]
+49 ÷ +6 = [ +8, +1 ]
+50 ÷ +6 = [ +8, +2 ]
+51 ÷ +6 = [ +8, +3 ]
+52 ÷ +6 = [ +9, −2 ]
+53 ÷ +6 = [ +9, −1 ]
+54 ÷ +6 = [ +9,  0 ]

The advantage of rounding Q to an even number in the halfway cases is that in a long series of calculations:

An equivalent alternative, in the halfway cases, is to consistently round Q to a number that is odd rather than even.


Two areas invite future research.

1. With Gaussian integers (in other words complex numbers whose real and imaginary parts are integers) there can be more than two combinations fulfilling the two key constraints; how to organize them is not obvious. Example:

(+17, +4) ÷ (−2, +3) = [ (−2, −5), (−2,  0) ]
or
(+17, +4) ÷ (−2, +3) = [ (−2, −4), (+1, +2) ]
or
(+17, +4) ÷ (−2, +3) = [ (−1, −5), ( 0, −3) ]
or
(+17, +4) ÷ (−2, +3) = [ (−1, −4), (+3, −1) ]

2. When multiplication is noncommutative, as with quaternions, the first of the two key constraints can be expected to have two variants:

Q × D + R = N
or
D × Q + R = N

while the second will likely require no change:

| R | < | D |