# Understanding the Recursive Algorithm for Integer Division

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 ?

• If it helps, the division algorithm is identical to long division in binary. Commented Sep 20, 2023 at 1:54

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. This step follows from the fact that $$2r'<2y$$.

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

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$$.

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, so that the quotient is zero.

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 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)$$.