How to multiply 2 Binary Numbers?

331 Views Asked by At

Suppose I have two regular numbers $a$ and $b$ in base $10$ like this: (where $N$ is even)

$$a=a_{\frac N2}a_{\frac N2-1}\ldots a_1,\qquad b=b_{\frac N2}b_{\frac N2-1}\ldots b_1$$

So the result of their multiplication is:

$$a\cdot b=a_{\frac N2}a_{\frac N2-1}\ldots a\cdot b_{\frac N2}b_{\frac N2-1}\ldots b_1=\sum_{i=1}^{\frac N2}\sum_{j=1}^{\frac N2}(a_ib_j)10^{i+j-2}$$


Now suppose $a=a_Na_{N-1}...a_1$ and $b=b_Nb_{N-1}...b_1$ are (unsigned) binary numbers, such that each digit is actually 16 bits by its own. For example: $a_1$ can be: $1111010101000000$

So if $a$ has $N$ digits it's actually: $16N$ long binary number.

Given this fact how can I multiply them in a similar way to what is shown above?

Why I need this?

I want to multiply big numbers using the fact that I know only to multiply 16 bits binary numbers.


Small But Different Example:

if $a_M, b_M, a_L, b_L$ are all 16 bits binary numbers then I could use this fact to multiply 32 bits numbers like this:

enter image description here

2

There are 2 best solutions below

7
On BEST ANSWER

In base $10$, the digit $a_1$ can take values from $0$ to $9$. Any numbers higher than that can only displayed if you also use $a_2$. In your setting, $a_1$ can take values from $0$ to $65535$ (which is $1111111111111111$ in binary). Any numbers higher than that can only displayed if you also use $a_2$. So, in summary, we should consider base $65536$ (instead of base $10$).

The formula becomes $$a\cdot b=a_{\frac N2}a_{\frac N2-1}\ldots a\cdot b_{\frac N2}b_{\frac N2-1}\ldots b_1=\sum_{i=1}^{\frac N2}\sum_{j=1}^{\frac N2}(a_ib_j)65536^{i+j-2},$$ where instead of $65536^{i+j-2}$ we can also write $(2^{16})^{i+j-2}$, which is the same as $2^{16 (i+j-2)}$. The number $16 (i+j-2)$ in the exponent of the last expressions is the number of bits that you need to shift by. to do (because if you multiply by $2^k$ this corresponds to a shift by $k$ bits).

2
On

Replace $10$ by the base $b$, either 2 or 16 or whatever to get

$a\cdot b=a_{\frac N2}a_{\frac N2-1}\ldots a\cdot b_{\frac N2}b_{\frac N2-1}\ldots b_1=\sum_{i=1}^{\frac N2}\sum_{j=1}^{\frac N2}(a_ib_j)b^{i+j-2} $.

If $b=2$, $b^{i+j-2}$ does $i+j-2$ left shifts.

If $b=16$, $b^{i+j-2}$ does $4(i+j-2)$ left shifts.