Number of digits in a binary product

Question

Assume i have 2 numbers in binary form (or, more precisely, assume to know the number of their digits, DF1, DF2):

101010101001010101010101010111111111111111111111010101 10101111111111111111010101

Is there a formula for the exact number of binary digits (DP) of the product?

  DP = F (DF1, DF2)

[I need this, in a practical case, to size a target array]

Answer 1

I assume you want to know the maximum possible bits that a product of two numbers might have. Under that assumption, let the first number $a$ have $m$ bits, and the second number $b$ have $n$ bits.

Then, $$a \leq 2^{m} - 1 $$ Similarly, $$b \leq 2^{n} - 1$$

Then, the product is: $$a \cdot b \leq 2^{m+n} - 2^m - 2^n + 1$$ Now, both $2^m$ and $2^n$ are greater than $1$ (since $n, m > 0$). So, $$a \cdot b < 2^{m+n} - 1$$

Therefore, at most $m+n$ bits are sufficient for the product of the two numbers. Of course, lesser bits might suffice. Also, the sign bit is not included in the computation, and each of $a$, $b$, and $a \cdot b$ might have a separate sign bit.

If you really need to optimize on space, you can check $a$ and $b$ for special cases. Some cases could be:

• $a$ or $b$ is $0$: You need 1 bit
• $a$ or $b$ is $1$: You need as many bits as the other number
• One of the numbers is a power of $2$: It will contain exactly one $1$, say at position $i$ (LSB is position 0). Then, the multiplication is equivalent to left shifting the other number by $i$ bits.

You might think up other special cases if you really need to.

Edit: As pointed out by Sam in the comments, if you impose the restriction that the most significant bit has to be 1 (unless the number itself is 0), you can get a lower bound too. Since the MSB is 1, we have: $$a \geq 2^{m-1}$$ and $$b \geq 2^{n-1}$$. Thus, $$a \cdot b \geq 2^{m + n - 2} = 2^{(m+n-1) - 1}$$

To represent $2^{(m+n-1)-1}$, you require $m+n-1$ bits, and so to represent $a \cdot b$, you need at least $m+n-1$ bits. This leaves the special case when either of the numbers is $0$, and assumes there are no leading 0's in any of the numbers.

As a conclusion, if you know the number of binary digits/bits of your number (as you mention in your question), you are most likely implying that there are no leading $0$'s and the left-most bit is $1$ (exception being when the number itself is 0, where you can simply assign 1 bit for the resulting product). In such a scenario, the product will have either $m+n$ bits or $m+n-1$ bits.

Answer 2

Let $a.b = c$

$\log a + \log b = \log c$

Length of a number $n$ in base $b$ is $\lceil \log_b (n + 1)\rceil$.

So $\lceil\log_2 (a + 1) + \log_2 (b + 1)\rceil$ bits should be enough.