# Very interesting method for multiplication of natural numbers [duplicate]

This question already has an answer here:

In some book I saw this example on how to multiply numbers $83$ and $157$.

$$83 \qquad 157$$ $$41 \qquad 314$$ $$20 \qquad 628$$ $$10 \qquad 1256$$ $$5 \qquad 2512$$ $$2 \qquad 5024$$ $$1 \qquad 10048$$

The procedure is that in the left column we divide numbers by two and write down the result under the number we divided (if the number is odd then we take integer which is closest to the result and less than the result) and we repeat the procedure until we arrive at the number one.

In the right column we just take the next number to be twice as big as the previous one.

Now we look at the two columns and discard those numbers in the right column if they correspond to the even number in the left column, so we discard $628$ and $1256$ and $5024$.

If we now add the remaining numbers in the right column we obtain $157+314+2512+10048=13031$ but $13031=83 \cdot 157$.

So my questions would be:

1) Does this method works for every two natural numbers $m,n$?

2) Can someone explain why this method works?

## marked as duplicate by Rob Arthan, Carsten S, Ross Millikan elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 13 '17 at 20:03

• Basically using binary multiplication. – DHMO Apr 13 '17 at 19:33
• Yes, this has been asked before. Let me find the link for you. – mathreadler Apr 13 '17 at 19:33
• 1) yes. 2) do you know the standard pencil-and-paper algorithm for multiplication? This is essentially the base 2 version of that algorithm combined with an easy way of working with decimal representations of the inputs and output. Doesn't the book give you any pointers? – Rob Arthan Apr 13 '17 at 19:33
• This known as Russian Peasant Multiplication I remember there being a question on the site about this, but I can't find it by name. – Tyberius Apr 13 '17 at 19:35
• Here is maybe the question Tyberius has in mind for russian peasant multiplication : math.stackexchange.com/questions/2099095/… – mathreadler Apr 13 '17 at 19:35

let's think that we want to multiply a by b.($a < b$)

Assume that a is an even number. Then $a * b = (a / 2) * (b * 2)$.

So as long as $a$ is even, we have no problem.

But when $a$ becomes odd, then we will have a problem. But we can solve it like this:

$a * b = (a / 2) * (b * 2) = (\lfloor a/2 \rfloor + 0.5) * (b * 2)$

So for simplification, in this methode, it recommends that you neglect that $0.5$ part and continue dividing and multiplying by 2, until $a$ becomes 1. But know, we have to add those $0.5$ parts. As you know $0.5 * b * 2 = b$. Which is the number in the right column.(The one we were multiplying by 2). So we add it up with the number we have at the end.

So it works for every $m, n \in \mathbb{R}$