# Problem about number representations

To multiply two numbers, such as 37 and 22, set up a table according to the following pattern.

\begin{array}{|c|c|} \hline 37&22 \\ \hline 18&44 \\ \hline 9&88 \\ \hline 4&176 \\ \hline 2&352 \\ \hline 1&704 \\ \hline \end{array}

The first column is formed by successive halvings (fractional remainders are discarded whenever they occur) and the second by successive doublings. If the elements of the second column standing opposite odd numbers in the first are added together, the result is 22+88+704=814= 22*37. Use the binary represenation to show that this rule is general.

So do I have to draw the same table and use the same pattern but with binary numbers?

• I presume from the wording that the binary relation is some kind of theorem or identity or process and that you are supposed to use it to prove that this method works. Perhaps the binary refers to how each odd or even number could be replaced by a 0 or 1? – The Great Duck Jun 21 '16 at 5:01
• So has any answer suited your interests? It is customary to accept an answer by clicking the little tick mark next to the post that best answers your question. – The Great Duck Jun 23 '16 at 18:45

Yes.   That is what you have to do.   Then think about why it is true.   Here, to get you started:

$$\begin{array}{|r:r|} \hline {10\,0101}&{1\,0110} & \star \\ \hdashline \\ \hdashline && \star \\ \hdashline \\ \hdashline \\ \hdashline 1 & 10\,1100\,0000 & \star\\ \hdashline \end{array}$$

Fill in the rest then think about it.   What is happening here?

• @TheMathNoob That is because you are expected to make some effort yourself. Fill in the other numbers in binary and you will see that you are carrying out binary multiplication. – almagest Jun 21 '16 at 6:02
• When I do normal binary multiplication I realized that the added numbers are the same numbers I add when I perform normal binary multiplication. – TheMathNoob Jun 21 '16 at 8:22
• @almagest his original answer was nothing more than "yes, you are correct." With absolutely NO explanation. That is why it was reported as low quality and why math noob complained. – The Great Duck Jun 21 '16 at 21:15
• @TheGreatDuck Ah, sorry. That shows the dangers of commenting an hour later! By the time I saw it, the answer looks sensible enough. – almagest Jun 21 '16 at 21:24
• I didn't complain. Thanks for your help guys!!!!!!! – TheMathNoob Jun 22 '16 at 6:53

Hint $\$ The algorithm amounts to computing integer products $\,n\times b\,$ by iteratively applying the following rewrite rules to reduce $\,n\,$ down to the trivial (base) case $\,n=1$.

$$\begin{eqnarray} (2a+\!1)\times b \,&=&\, a\times 2b\, \color{#c00}{+\, b}\ \ && \rm{i.e. when}\,\ 2a\!+\!1\,\ is\ \ \color{#c00}{odd}\\ (2a+\!0)\times b \,&=&\, a\times 2b\ \ && \rm{i.e. when}\,\ 2a\!+\!0\,\ is\ \ {even}\\ \end{eqnarray}$$

Remark $\$ Such multiplication by repeated doubling is just the multiplicative analog of exponentiation by repeated squaring, i.e.

$$\qquad\begin{eqnarray} b^{2a+1} \,&=&\, (b^2)^a \color{#c00}{\times\, b}\ \ && \rm{i.e. when}\,\ 2a\!+\!1\,\ is\ \ \color{#c00}{odd}\\ b^{2a+0} \,&=&\, (b^2)^a \ && \rm{i.e. when}\,\ 2a\!+\!0\,\ is\ \ {even}\\ \end{eqnarray}$$

This may be clearer if you view the radix representation in nested Horner form (as arises when it is computed by repeatedly dividing by $2$ with remainder), i.e.

$$n\, =\, d_0 + 2 (d_1 + 2( d_2 + \cdots + d_n))$$

When you half an even number whilst doubling the other number, multiplication is unaffected. This means you need not look at even valued rows as their cases will be handled below. When you reach an odd number, there is a reason why you keep that one in adding. It is because you toss away the remainder. When you do that, a value of (1*that current rows right value) is lost. Therefore, you must add it back at the bottom. In reality another to phrase it is this:

Divide one number by c when going down, and multiply the other by c.

Once you have reached some number in the left hand column less than c, do the following:

Let A denote a left value in a row, and let B denote a right value.

For all the rows add up all terms of the form: (A mod C) * B

In general, this process could be termed transferring factors and need not be limited to one particular item. In fact, it is common practice for me to try to balance two digit multiplication so that it becomes 1 digit multiplication times 2 digit multiplication.

Oh and these also happen to be the numbers you would add up in binary base 2 multiplication. However, I prefer rather to think of it as adding back the remainders you chopped off when transferring the factor 2.