# Algorithm Design Manual Question 1-7 [closed]

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

-
Wait, what now? Did you post a (homework) question and then answer it? –  Marc Khoury Feb 6 at 17:11
This site is not "post your homework, get it done for free". At least show that you really tried to solve the problem, and where you got stuck. –  vonbrand Feb 6 at 17:29
People don't really bother to scroll down a bit do they? I answered my own question at the same time I posted it. Part of the functionality of the stack exchange sites is the Q/A "share your knowledge" - answer your own question button which is at the bottom of every question as you are composing it. –  Robert S. Barnes Feb 6 at 18:54
I think you could make the question better by framing it in the form of a question more. Instead of just copying the assignment, what was difficult? Where are you (or were you) stuck? –  Juho Feb 6 at 20:57
I agree. Pasting exercises and answers here is not only barely in touch with what usually makes a question good for SE, it can get you into copyright trouble, too. If you look around on the site, you will find plenty of good questions and great answers to inspire you. –  Raphael Feb 6 at 22:24

## closed as not a real question by Marc Khoury, vonbrand, Merbs, Pål GD, Sasho NikolovFeb 7 at 17:45

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

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$

-
So, do you want us to evaluate your work by up/down votes ? –  AJed Feb 6 at 19:26
@AJed At this point I don't really care what people do. I was just trying to share something I thought might be helpful to someone else, and I've gotten a ton of grief for it. –  Robert S. Barnes Feb 6 at 20:42
Ah forget about what people say ! :) –  AJed Feb 6 at 21:41
It is really not clear what you mission is here. Is this a verified solution, i.e. one you consider correct? In any case, you should highlight the key items in order to be more helpful for future readers. –  Raphael Feb 6 at 22:25
@Raphael There are no answers in Skeina's book. He has a wiki with some partial answers, to a few questions, but that's it. For someone who's trying to learn independently ( such as myself ), it can be a real PITA if you get stuck and it helps immensely to see a fully worked out, formal solution. –  Robert S. Barnes Feb 7 at 4:18
show 1 more comment