1
$\begingroup$

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 ?

$\endgroup$
1
  • 1
    $\begingroup$ If it helps, the division algorithm is identical to long division in binary. $\endgroup$
    – Pseudonym
    Sep 20, 2023 at 1:54

4 Answers 4

2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.