Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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]

share|improve this question

migrated from cstheory.stackexchange.com Dec 20 '12 at 14:31

This question came from our site for theoretical computer scientists and researchers in related fields.

    
would it be right guessing DF1 + DF2 + 1 (thinking about the shifts) ? –  Pam Dec 20 '12 at 12:23
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
If you require that the leftmost digit of both $a$ and $b$ is one you can get a lower bound using essentially this exact same method –  SamM Dec 20 '12 at 19:05
    
@Sam Thanks! I did not give the lower bound as the OP needs to allocate memory for an array, and needs an upper bound on the number of bits. But I have edited the answer, as the lower bound shows that unless the product is 0, the number of bits do not have a big range. Also, the lower bound removes the need of the special cases that I mentioned, except for the special case of product being 0. I have edited my answer with the lower bound. –  Paresh Dec 20 '12 at 19:46
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.