World's most popular travel blog for travel bloggers.

# [Answers] Why does russian peasant multiplication work?

, ,
Problem Detail:

can someone provide a proof with induction on why the Russian peasant multiplication work ?

if you don't know what that is , here is the algorithm :

                    P(2·a,⌊b/2⌋)   : b>1 and b is even number P(a,b):=            P(2·a,⌊b/2⌋)+a : b>1 and b is odd number                      a              :b=1 

#### Answered By : melchizedek

Let $a \cdot b = p \cdot q + r$.

What's the base case for the induction? $p = a, q = b, r = 0$.

Inductive step: $a \cdot b = p \cdot q + r$ holds, then $a \cdot b = p' \cdot q' + r'$ in the next iteration.

Case 1: $p$ is odd. If $p$ is odd, then $p' = \frac{p-1}{2}, q' = 2q, r' = r + q$

$$p' \cdot q' + r' = \frac{p - 1}{2} \cdot 2q + r + q = pq - q + q + r = pq + r = a \cdot b$$

Case 2: $p$ is even. Then $p' = \frac{p}{2}, q' = 2q, r' = r$

That also implies $p' \cdot q' + r' = p \cdot q + r = a\cdot b$

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65170

3.2K people like this