SI242: The division algorithm

The division algorithm

We don't have a division operator over the integers, but we do have a different notion of division: dividing $a$ by $b$ gives us a quotient and a remainder. You may remember the idea of quotient and remainder from grade school, but you probably haven't used it much since. But it turns out to be very important to understanding the integers. Here is a very simple (not efficient) algorithm for computing the quotient and remainder of two numbers. It literally corresponds to the idea of "how many times does $b$ go into $a$, and what's leftover when you are done?

Algorithm: div	
Inputs: a, b where a>=0 and b>0
Output: q and r such that a = q*b + r, and 0 ≤ r < b
if a < b
  q = 0, r = a
else
  q',r' = div(a-b,b)
  q = q'+1, r = r'
return q,r

Just to make sure you understand how this works, here's an example:

                           a   b   q'  r'  q   r 
                           --------------------- 
initial call is div(27,6)  27  6   3   3   4   3

makes a call to div(21,6)  21  6   2   3   3   3

makes a call to div(15,6)  15  6   1   3   2   3

makes a call to  div(9,6)   9  6   0   3   1   3

makes a call to  div(3,6)   3  6   -   -   0   3

The first three lines of the algorithm (before any actual steps to execute) are what is called the specification of the algorithm. It tells you what kinds of inputs are allowed, and what properties the outputs will satisfy. After that is the body of the algorithm. We can't just assume that the algorithm actually accomplishes what the specification states. We need to prove it! We need to prove that if we give two integers $a$ and $b$ that satisfy the requirements that $a \geq 0$ and $b > 0$, then $\text{div}(a,b)$ will return $p$ and $q$ such that $a = q*b+r$ and $0\leq r \lt b$. We are going to want to do this by induction, but that means that we need to define what the "size" of $\text{div}(a,b)$ is. We are going to adopt a somewhat strange idea of size:

size of $\text{div}(a,b)$ is 0 if $a \lt b$ and $1 + a - b$ otherwise

To get an idea of what this means, let's see the sizes of the calls to div in the above example:

                           a   b   q'  r'  q   r   size
                           --------------------- 
initial call is div(27,6)  27  6   3   3   4   3    22 ← 1 + 27 - 6

makes a call to div(21,6)  21  6   2   3   3   3    16 ← 1 + 21 - 6

makes a call to div(15,6)  15  6   1   3   2   3    10 ← 1 + 15 - 6

makes a call to  div(9,6)   9  6   0   3   1   3    4 ← 1 + 9 - 6

makes a call to  div(3,6)   3  6   -   -   0   3    0 ← a < b

Notice how the sizes get smaller and smaller with each successive call to div, and that it bottoms out at size 0. That shows us that we have chosen a good definition of "size".

(Correctness of div) The division algorithm meets is specifications, i.e. given $a\geq 0$ and $b > 0$, calling $\text{div}(a,b)$ returns values $q$,$r$ such that $a = q*b+r$ and $0\leq r \lt b$.

We proceed by induction, where the "size" of $\text{div}(a,b)$ is 0 if $a \lt b$ and $1 + a - b$ otherwise.
If size of $\text{div}(a,b)$ is equal to $0$, then $a \lt b$, so div returns $q=0$,$r = a$ and $q*b+r = 0*b + a = a$. ✓
If size of $\text{div}(a,b)$ is greater than $0$, then $a \geq b$ so the algorithm sets $q',r' = \text{div}(a-b,b)$. Since size $\text{div}(a-b,b)$ is less than size $\text{div}(a,b)$, we can apply the inductive hypothesis, which guarantees that $q',r'$ satisfy $a-b = q'*b + r'$ and $0 \leq r' \lt b$. Adding $b$ to both sides of this gives us
$a = q'*b + r' + b = \underbrace{(q'+1)}_{q}*b + \underbrace{r'}_{r}$
so the $q,r$ returned by div satisfies $a=q*b+r$. ✓

ACTIVITY ← verifying the correctness of the above proof!

Here's an important question that you probably never considered in grade school math: are the quotient and remainder unique? Or are there choices? For example: if a=27 and b=6, the quotient is 4 and remainder is 3, since: 27 = 4*6 + 3. But are there other choices? It turns out the answer is "no"!

(Uniqueness of quotient and remainder) For any two non-negative integers $a$ and $b$, where $b \neq 0$, there are unique integers $q$ and $r$, called the quotient and remainder, such that $ a = q*b + r $ and $0 \leq r \lt b$.

The previous thoerem shows that $q$ and $r$ satisfying $a = q*b+r$ and $0\leq r \lt b$ exist. So what remains to be shown is uniqueness, i.e. that there is no different pair of numbers satisfying that relationship for $a$ and $b$. Suppose $q',r'$ also satisfy $a = q'*b+r'$ and $0 \leq r' \lt b$. Assume $r \geq r'$ (if not just swap the names of $q,r$ and $q',r'$). Then $q*b+r = q'*b+r'$, which we can rewrite as $r-r' = (q'-q)*b$. Note that $0 \leq r-r' \lt b$, and that $b|r-r'$. If $r-r' \neq 0$, then by the "Divisors are smaller" theorem (above) $b \leq r-r'$, which is a contradiction. So $r-r' = 0$, which means $q'-q=0$, which means that $r,q$ and $r',q'$ are the same.

Quotient and remainder with negative numbers

It's not necessarily clear how to define quotient and remainder when $a$ and/or $b$ are negative. When $a \lt 0$ and $b > 0$, it still makes sense to ask for the remainder, $r$, to satisfy $0 \leq r \lt b$. So if we stick with that, we get, for example, that "dividing" -27 by 6 should give us quotient -5 and remainder 3, since $-27 = -5 \cdot 6 + 3$. [Note: when the dividend $a$ is negative and the divisor $b$ is positive, as in this case, you just compute $q',r' = \text{div}(-a,b)$, then set $q = -q' - 1, r = -r' + b$.] But what about when the divisor is negative? We will adopt the convention that the remainder when dividing $a$ by $b$, where $b \neq 0$, satisfies $0 \leq r \lt |b|$.

Given integers $a$ and $b$, with $b \neq 0$, the quotient and remainder are the unique integers $q$ and $r$, respectively, that satisfy $a = q*b + r$ and $0 \leq r \lt |b|$.

Warning! Everyone agrees on the definition of quotient and remainder when neither $a$ nor $b$ are negative. However, there are at least three different definitions out there when negative values come into play ... and that includes different ideas from different programming languages. Note that in C++, the '/' operator on objects of type int is for quotient, the '%' operator is for remainder. In Python, the '//' operator is for quotient and '%' is for remainder.

sign of q,r for SI242
       a > 0   a < 0
b > 0  q+,r+   q-,r+
b < 0  q-,r+   q+,r+

sign of q,r for C++	  
       a > 0   a < 0
b > 0  q+,r+   q-,r-
b < 0  q-,r+   q+,r-

sign of q,r for Python
       a > 0   a < 0
b > 0  q+,r+   q-,r+
b < 0  q-,r-   q+,r-

ACTIVITY ← We didn't do this activity (spent our time on the first one instead)
Write a C++ program that reads in integers a and b and prints "error!" if b = 0, and otherwise prints out a = q*b + r with the appropriate values for our SI242 definition of quotient and remainder. Note: use the C++ / and % operators, but correct for negative values of a and/or b.

-27 6
-27 = -5*6 + 3