Why does russian peasant multiplication work? [duplicate]

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

• If P(a,b)=ab then P(2*a,b/2)=(2*a)*(b/2) = ab (assuming b is even : (b/2)*2=b). You can prove the equivalences, then, iteratively dividing b will converge towards 1, so the suite will eventually converge to a*b. – TEMLIB Oct 26 '16 at 23:59
• i was able to prove it assuming b is even , but the problem is when b is odd or b-1 it doesn't not equal . – Dana10 Oct 27 '16 at 0:05
• Please don't repost the exact same question. – Raphael Oct 27 '16 at 0:09

1 Answer

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$

• Please consider not to encourage undesirable posting behaviour. – Raphael Oct 27 '16 at 0:08
• Also, the OP posted the exact same question before. – Raphael Oct 27 '16 at 0:08
• @Raphael can you please explain why r′=r+q , why exactly +q – Dana10 Oct 27 '16 at 16:01
• You should look at your recursion. – Aristu Oct 27 '16 at 19:56