**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 `

###### Asked By : Dana10

#### 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**

## 0 comments:

## Post a Comment

Let us know your responses and feedback