patternMinor
Number of digits in a binary product
Viewed 0 times
digitsnumberbinaryproduct
Problem
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?
[I need this, in a practical case, to size a target array]
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]
Solution
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
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.
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
- $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.
Context
StackExchange Computer Science Q#7525, answer score: 5
Revisions (0)
No revisions yet.