Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What exactly happens with the remainder in this algorithm? I don't understand why it is "dropped".

Example:

$$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline 38&\times&15&1\\ 18&\times&30&1\\ 9&\times&60\\ 4&\times&120\\ 1&\times&480 \end{array}$$

What is happening with the $1$'s???

share|improve this question
2  
I assume that you’re talking about what is sometimes called Russian peasant multiplication; you should make this clear in the question. –  Brian M. Scott May 22 '12 at 21:48
    
Meh, cross-editing. –  Phira May 22 '12 at 21:52
    
@Jennifer: First of all, the half of 38 is not 18. And please explain what your question is. Do you not know how to proceed or do you not understand why it works? –  Phira May 22 '12 at 21:55
2  
As Phira says, half of $38$ isn’t $18$; moreover, there’s no remainder there, or when taking half of $18$, but there is a remainder when taking half of $9$. –  Brian M. Scott May 22 '12 at 21:57
1  
Welcome to Math.SE Jennifer. –  AD. May 22 '12 at 21:59

2 Answers 2

I think that you’ve some misconceptions about both the workings of the algorithm and the reason it works.

Let’s look in detail at $37\cdot 15=555$. Here’s the correct table, in the arrangement that you used in your question, but with a little more detail. (Ignore the underlines and the $\text{Row}$ column for now.)

\begin{array}{c|cc} \text{Row}&\text{Half}&&\text{Double}&\text{Remainder}\\ \hline 0&37&\times&\underline{15}&1\\ 1&18&\times&30&0\\ 2&9&\times&\underline{60}&1\\ 3&4&\times&120&0\\ 4&2&\times&240&0\\ 5&1&\times&\underline{480}&1 \end{array}

There’s a remainder in the last line because $1$ would leave a remainder if you went on to halve it.

Ignore the $\text{Double}$ column for now. The first and last columns tell you that

$$\begin{align*} 37&=2\cdot 18+1\\ &=2(2\cdot 9+0)+1\\ &=2^2\cdot9+1\\ &=2^2(2\cdot4+1)+1\\ &=2^3\cdot4+2^2+1\\ &=2^3(2\cdot2+0)+2^2+1\\ &=2^4\cdot2+2^2+1\\ &=2^5+2^2+1\;. \end{align*}\tag{1}$$

In other words, they show how to express $37$ as a sum of powers of $2$, i.e., how to write it in binary (base two) notation: $37=1\cdot2^5+0\cdot2^4+0\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0$, so in binary it’s $100101$.

Now read the $\text{Remainder}$ column from bottom to top: $100101$. It’s exactly the same. And if you examine closely the calculations in $(1)$ and think about how they’re related to the original table, you’ll see that this will always work: the $\text{Remainder}$ column, read from bottom to top, gives you the binary representation of the number that you’re halving.

Now, finally, we’ll look at what’s happening in the $\text{Double}$ column. We want $37\cdot15$. We now know that $37=2^5+2^2+1$, so

$$\begin{align*} 37\cdot 15&=(2^5+2^2+1)\cdot 15\\ &=2^5\cdot15+2^2\cdot15+1\cdot15\;. \end{align*}$$

Now $2^5\cdot15=\underbrace{2\cdot2\cdot2\cdot2\cdot2}_{5\text{ twos}}\cdot15$ is what you get when you double $15$ five times, $2^2\cdot15$ is what you get when you double $15$ twice, and of course $1\cdot15$ is just the original $15$. The $\text{Row}$ column of the table shows how many doublings (and halvings) have been performed to get to a given row, so are the numbers that I underlined in the $\text{Double}$ column. Thus,

$$\begin{align*} 37\cdot 15&=(2^5+2^2+1)\cdot 15\\ &=2^5\cdot15+2^2\cdot15+1\cdot15\\ &=480+60+15\\ &=555\;. \end{align*}$$

Notice that these are also the numbers in the $\text{Double}$ column adjacent to $1$’s in the $\text{Remainder}$ column. That’s no accident: those $1$’s showed which powers of $2$ were needed to make up the multiplier $37$, and therefore which compound doublings of $15$ must be added to get the product.

The whole idea is use the repeated halving of the multiplier to write it as a sum of powers of two, because multiplying another number, like $15$, by a power of $2$ is easy: $2^na$ is what you get when you double $a$ $n$ times, and doubling is easy. The remainders of $1$ aren’t really lost: they tell you which powers of $2$ are actually needed in the binary representation of the multiplier and thereby tell you which doublings of the other number must be added together to get the product.

share|improve this answer

This is a method for multiplication? Well, in the ideal case, we can precisely halve one side, and double the other:

$4\times120 = 2\times240 = 1\times480$

However, in some cases, we cannot exactly halve, because we have an odd number to halve. We can deal with this by having a remainder:

$9\times60 = 4\times120 + 60$. So, we have an additional 60 that is not dealt with - so we'll ignore it for now, keep going, and add 60 to the final result later on.

I'm not exactly clear about your method, but I assume it would be better as follows:

$$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline 38&\times&15&\\ 19&\times&30&\\ 9&\times&60&30\\ 4&\times&120&60\\ 1&\times&480 \end{array}$$

So, the result will be $38 \times 15 = 480 + 60 + 30 = 570$

This algorithm would seem to be quicker if we halved the smaller number. But, this leads to two problems - 38 is harder to double than 15 (which would double to a multiple of 10), and because 15 is just one below 16 (a power of 2), meaning we get a lot of nasty remainders:

$$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline 15&\times&38&\\ 7&\times&76&38\\ 3&\times&152&76\\ 1&\times&304&152\\ \end{array}$$

It seems like we did one less step of work. But, the result is $15 \times 38 = 308+154+76+38 = 570$. Yuck! This way around doesn't make it simple to calculate by hand.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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