4
$\begingroup$

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???

  • 1
    Welcome to Math.SE Jennifer.2012-05-22

2 Answers 2

5

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.

1

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.