If you want to make money online : Register now

[Answers] Why does russian peasant multiplication work?

, , No Comments
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

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback