-1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – TEMLIB Oct 26 '16 at 23:59
  • $\begingroup$ 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 . $\endgroup$ – Dana10 Oct 27 '16 at 0:05
  • 2
    $\begingroup$ Please don't repost the exact same question. $\endgroup$ – Raphael Oct 27 '16 at 0:09
0
$\begingroup$

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$

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.