3
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ in each iteration, the number in the left column decreases by a factor of 10 and the right column increases by a factor of 10. You either move the dot to the left or right. That's all I see. $\endgroup$
    – TheMathNoob
    Jun 21, 2016 at 5:49
  • 1
    $\begingroup$ @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. $\endgroup$
    – almagest
    Jun 21, 2016 at 6:02
  • 1
    $\begingroup$ When I do normal binary multiplication I realized that the added numbers are the same numbers I add when I perform normal binary multiplication. $\endgroup$
    – TheMathNoob
    Jun 21, 2016 at 8:22
  • 1
    $\begingroup$ @TheGreatDuck Ah, sorry. That shows the dangers of commenting an hour later! By the time I saw it, the answer looks sensible enough. $\endgroup$
    – almagest
    Jun 21, 2016 at 21:24
  • 1
    $\begingroup$ I didn't complain. Thanks for your help guys!!!!!!! $\endgroup$
    – TheMathNoob
    Jun 22, 2016 at 6:53
2
$\begingroup$

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)) $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .