Algorithm Design Manual Question 1-7 [closed]

Question

Skeina, The Algorithm Design Manual

Question 1-7.

Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants c ≥ 2.

function mul(y, z)

// Return the product yz.

if z = 0 then return(0) else
return ( mul(cy, floor(z/c) ) + y * (z mod c) )

Answer 1

Assume that $c \geq 2,y,z\in\mathbb{N}$

We will prove by induction on $z$ that mul(y,z) = yz.

For $z=0$, the algorithm is trivially true.

For $z=1$ we have: $mul(y,1)$

$= mul(cy, \lfloor\frac{1}{c}\rfloor) + y( 1 \mod c )$

$= mul(cy, 0) + y( 1 \mod c )$

$= 0 + y * 1$ since according to our assumption $c \geq 2$

$= y*1$

Assume that for $z=k$ where $k\ge 1 \in \mathbb{N}$ the above is true and we will prove for $z=k+1$.

We have that $mul(y, k+1) = mul(cy, \lfloor\frac{k+1}{c}\rfloor) + y( (k+1) \mod c )$

We will show that $\lfloor\frac{k+1}{c}\rfloor \leq k$

Since according to our assumption $c \geq 2$ we have that

$$2k \leq ck \Leftrightarrow \frac{2k}{c} \leq k \Leftrightarrow \frac{k+k}{c} \leq k \Leftrightarrow \frac{k}{c} + \frac{k}{c} \leq k$$

Since $c \geq 2$, we have that $\frac{1}{c} <= \frac{k}{c}$ and the following holds:

$$\lfloor\frac{k+1}{c}\rfloor \leq \frac{k+1}{c} = \frac{k}{c} + \frac{1}{c} \leq \frac{k}{c} + \frac{k}{c} \leq k$$

Therefore according to the induction assumption:

$$mul(cy, \lfloor\frac{k+1}{c}\rfloor) = cy * \lfloor\frac{k+1}{c}\rfloor$$

and we have:

$$mul(y, k+1 ) = cy * \lfloor\frac{k+1}{c}\rfloor + y( (k+1)\mod c )$$

$$ = y * [ c * \lfloor\frac{k+1}{c}\rfloor + (k+1)\mod c ]$$

By definition of the floor function:

$$\lfloor\frac{k+1}{c}\rfloor = \frac{(k+1) - [(k+1)\mod c]}{c}$$

So:

$$= y * \left [ c * \frac{ (k+1) - \left [(k+1)\mod c \right ]}{c } + (k+1)\mod c \right ]$$

$$= y * \left [ k+1 - [(k+1)\mod c] + [(k+1)\mod c] \right ]$$

$$= y * (k+1)$$

$\blacksquare$