Understanding the Recursive Algorithm for Integer Division

Question

In my reference, Page 26, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, a division algorithm is give as, \begin{align} &\text{function divide}(x, y)\\\\ &\text{Input: Two n-bit integers x and y, where }y ≥ 1\\\\ &\text{Output: The quotient and remainder of x divided by y}\\\\ \\\\ &\text{if $x = 0$: return $(q, r) = (0, 0)$}\\\\ &\text{$(q, r)$ = divide$(\lfloor x/2\rfloor, y)$}\\\\ &\text{$q = 2 · q, r = 2 · r$}\\\\ &\text{if $x$ is odd: $r = r + 1$}\\\\ &\text{if $r ≥ y: r = r − y, q = q + 1$}\\\\ &\text{return $(q, r)$}\\\\ \end{align}

I am trying to understand the internal mathematical working of this recursive algorithm for division.

There is a similar recursive algorithm for multiplication given in my reference,

\begin{align} &\text{function multiply $(x, y)$}\\\\ &\text{Input: Two n-bit integers $x$ and $y$, where $y≥0$}\\\\ &\text{Output: Their product}\\\\ \\\\ &\text{if $y = 0$: return $0$}\\\\ &\text{$z$ $=$ multiply$(x, by/2c)$}\\\\ &\text{if $y$ is even:}\\\\ &\quad\text{return $2z$}\\\\ &\text{else:}\\\\ &\quad\text{return $x + 2z$}\\\\ \end{align} The operation of the multiplication algorithm can be understood as follows: $$ x.y=\begin{cases} 2(x.\lfloor y/2\rfloor)\text{ if }y\text{ is even}\\\\x+2(x.\lfloor y/2\rfloor)\text{ if }y\text{ is even} \end{cases} $$ which can be verified as, \begin{align} y&=2n\implies 2(x.\lfloor y/2\rfloor)=2(x.\lfloor n\rfloor)=2xn=x.2n=xy\\\\ y&=2n+1\implies x+2(x.\lfloor y/2\rfloor)=x+2(x.\lfloor n+1/2\rfloor)=x+2xn=x(1+2n)=xy \end{align}

But is it possible to understand the given division algorithm in a similar way ?

Answer 1

Suppose $x$ is divided by $y$, and the quotient is $q$ and remainder is $r$. Then, it means the following:

$$x = q \cdot y + r \quad \quad \textrm{where} \quad r < y. \quad \quad (1)$$

Consider the case when $x = even$. Then, $x = 2x'$. Suppose that $x'$ when divided by $y$ gives quotient $q'$ and remainder $r'$. Then, we have:

$$x = 2x' = 2 \cdot (q'\cdot y + r') \quad \quad \textrm{where} \quad r' < y. \quad \quad (2)$$

By equation $(1)$, we have

1. for $2r' < y$, we get $q = 2q'$ and $r=2r'$.
2. for $2r' > y$, we get $q = 2q'+1$ and $r=2r'-y<y$. This step follows from the fact that $2r'<2y$.

You can show a similar proof for $x = odd$.

Answer 2

The division algorithm You are trying to understand is basically a recursive description of good old long division, albeit in binary form. You can think of the following line:

$$ (q,r) = divide(\lfloor x/2\rfloor,y) $$

As moving the divisor $y$ one binary digit to the left. This is done recursively until the least significant digit of $y$ is left of the most significant digit of $x$. From there the actual long division starts by repeatedly shifting in the next bit of $x$, determining the next bit of the quotient $q$, all the while keeping track of the remainder $r$.

Answer 3

Instead of directly dividing $x$ by $y$, you divide $x\div 2$ by $y$ and multiply the quotient by $2$. This gives an approximate quotient, and the rest of the computation is a correction to get the true quotient, which may be off by one unit ($x\div y=2( (x\div2)\div y)$ or $2( (x\div2)\div y)+1$). Notice that $x\div2$ amounts to dropping the least significant bit of $x$.

This principle is applied recursively, up to the moment that $x<y$, so that the quotient is zero.

Answer 4

One can prove by induction on $x\ge 0$ that $$(q,r) =\text{divide}(x,y)\Longrightarrow x=q y + r\text{ and }0\le r\le y-1$$ Indeed this is true when $0=x$ because $0=0.y + 0$. When $1\le x$, first note that $2\le x+[x\text{ odd}]$, where $[\text{ }]$ is Iverson's bracket, hence $$0\le\left\lfloor\frac{x}{2}\right\rfloor= \frac{x-[x\text{ odd}]}{2}\le\frac{x + (x-2)}{2}= \frac{2x-2}{2}=x-1<x$$ So after $(q, r) = \text{divide}(\left\lfloor\frac{x}{2}\right\rfloor,y)$, the induction hypothesis implies that $$\frac{x-[x\text{ odd}]}{2}=q y+r\quad\text{and}\quad 0\le r\le y-1$$ Hence $$x= (2q)y + (2 r +[x\text{ odd}])$$ If $2 r +[x\text{ odd}]< y$, this is an euclidean division of $x$ by $y$ and the algorithm correctly returns $(2q, 2 r +[x\text{ odd}])$ to satisfy the induction hypothesis. When $y \le 2 r +[x\text{ odd}]$, one can write $$x= (2q+1)y + (2 r +[x\text{ odd}]-y)$$ and it holds $$0\le 2 r +[x\text{ odd}]-y\le 2(y-1)+[x\text{ odd}]-y\le y-1$$ so this is again an euclidean division an the algorithm correctly returns $(2q+1, 2 r +[x\text{ odd}]-y)$.