0

I was reading this awesome book called "Algorithms" by "Jeff Erickson" and I came across this peasant multiplication

enter image description here

he said it works because enter image description here

How can I prove the second statement by induction and what's the intuition behind it?

EDIT: I understand that there are multiple easier proofs, I'm trying to get a sense of how induction works in this case.

ViktorStein
  • 4,838
Ahmed I. Elsayed
  • 217
  • 1
    Why use induction? If $x$ is odd then $x=2n+1$ for some $n$ and $\lfloor \frac x2\rfloor=n$ We then get $(2n+1)y$ on the left and $2ny+y$ on the right. – lulu Mar 01 '21 at 12:28
  • 1
    With all respect: induction is not needed to prove the formula above, but it is needed to prove that $x*y=x\cdot y$. –  Mar 01 '21 at 12:29
  • @lulu Thank you for your proof and time, I just wanted to understand how can I use induction with 2 variables in this context – Ahmed I. Elsayed Mar 01 '21 at 12:34
  • @StinkingBishop I think the author only meant multiplication as he's talking about multiplication algorithms (currently peasant) – Ahmed I. Elsayed Mar 01 '21 at 12:34

2 Answers2

1

If $x$ is even,

$$xy=\frac x22y$$ is immediate.

Now if $x$ is odd,

$$(x-1)y=\frac{x-1}22y$$ and $$xy=\left\lfloor\frac x2\right\rfloor2y+y.$$

The rationale behind the algorithm becomes clear if you expand $x$ as a binary number

$$x=\sum_{k=0}^nb_k2^k$$ where the $b_k$ are $0$ or $1$.

Now

$$xy=\sum_{k=0}^n(b_k2^k)y=\sum_{k=0}^nb_k(2^ky).$$

1

On one hand:

$$x\cdot y=\begin{cases}0&x=0\\\lfloor x/2\rfloor\cdot(y+y)&x\text{ even}\\\lfloor x/2\rfloor\cdot(y+y)+y&x\text{ odd}\end{cases}$$

which can be proven directly (distinguishing cases $x=2n, \lfloor x/2\rfloor=n$ and $x=2n+1, \lfloor x/2\rfloor=n$).

On the other hand:

$$x*y=\begin{cases}0&x=0\\\lfloor x/2\rfloor*(y+y)&x\text{ even}\\\lfloor x/2\rfloor*(y+y)+y&x\text{ odd}\end{cases}$$

as per the "Peasant's Algorithm". Note this recurrence is almost the same as the previous one, except $\cdot$ (the ordinary multiplication symbol) is replaced by $*$.

How do we prove that $x\cdot y=x*y$ for all $x,y$? Take induction on $x$, and in fact take what is often called "transfinite" induction: assuming the statement to be true for all $0,1,\ldots,x-1$ (rather than just for $x-1$) you prove that it is valid for $x$.

Now:

$$0\cdot x=0=0*x$$

and, for $x>0$ we have $\lfloor x/2\rfloor<x$, so:

$$\begin{array}{rcll}x\cdot y&=&\begin{cases}0&x=0\\\lfloor x/2\rfloor\cdot(y+y)&x\text{ even}\\\lfloor x/2\rfloor\cdot(y+y)+y&x\text{ odd}\end{cases}\\&=&\begin{cases}0&x=0\\\lfloor x/2\rfloor*(y+y)&x\text{ even}\\\lfloor x/2\rfloor*(y+y)+y&x\text{ odd}\end{cases}&\text{Apply inductive hypothesis to }\lfloor x/2\rfloor\\&=&x*y\end{array}$$

which is the inductive step (assuming the operators$\cdot$and $*$ match for $\lfloor x/2\rfloor$, proving that it is valid for $x$).