if two n bit numbers are multiplied then the result will be maximum how bit long

Question

I was wondering if there is any formula or way to find out much maximum bits will be required if two n bits binary number are multiplied. I searched a lot for this but was unable to find its answer anywhere.

Possible duplicate of [Multiplication of two 16-bit numbers - Why is the result 32-bit long?](https://stackoverflow.com/questions/21416792/multiplication-of-two-16-bit-numbers-why-is-the-result-32-bit-long) — phuclv, Jul 09 '18 at 16:46

score 13 · Answer 1 · answered Sep 13 '13 at 16:04

Number of digits in base B required for representing a number N is floor(log_B(N)+1). Logarithm has this nice property that log(X*Y)=log(X)+log(Y), which hints that the number of digits for X*Y is roughly the sum of the number of digits representing X and Y.

score 10 · Accepted Answer · edited Jun 20 '20 at 09:12

10

It can be simply concluded using examples:

11*11(since 11 is the maximum 2 bit number)=1001(4 bit)

111*111=110001(6 bit)

1111*1111=11100001(8 bit)

11111*11111=1111000001(10 bit)

and so from above we can see your answer is 2*n

edited Jun 20 '20 at 09:12

Community

1
1

answered Sep 13 '13 at 15:31

Thank-you it was simple to get it – Sep 13 '13 at 15:48
13

Simple conclusion using examples is not, generally speaking, a good idea. – Michael Sep 13 '13 at 15:50
But is helpful for better understanding – Sep 13 '13 at 15:54
But it is not a proof. – Coder Nov 23 '20 at 04:31
if there are n and m bits involved, then simply add n and m: n+m bits. – 0zkr PM Jun 22 '21 at 22:40

score 8 · Answer 3 · answered Sep 13 '13 at 15:32

8

The easiest way to think about this is to consider the maximum of the product, which is attained when we use the maximum of the two multiplicands.

If value x is an n-bit number, it is at most 2^n - 1. Think about this, that 2^n requires a one followed by n zeroes.

Thus the largest possible product of two n-bit numbers will be:

(2^n - 1)^2 = 2^(2n) - 2^(n+1) + 1

Now n=1 is something of a special case, since 1*1 = 1 is again a one-bit number. But in general we see that the maximum product is a 2n-bit number, whenever n > 1. E.g. if n=3, the maximum multiplicand is x=7 and the square 49 is a six-bit number.

answered Sep 13 '13 at 15:32

hardmath

8,753
2
37
65

Nice!! maybe 2n is due to taking log2. log2(2^(2n) - 2^(n+1) + 1) ~ log2(2^(2n)) = 2n. – Pulkit Agarwal Jul 15 '14 at 17:50
@hardmath I realized that as I posted, however, by your formula (using the right-hand side), I still get the wrong answer. Suppose I multiply 7 * 7 in binary: 111 * 111 = 110001. Your formula says: 2^(2*3) - 2^(3+1) + 1 = 49. That is the maximum *value*, NOT the maximum length in bits (which is what the question asked for), and which is 6. – EntangledLoops Mar 15 '15 at 21:24
@hardmath One other minor thing: you said to think of it as 2^n "followed by n zeroes", but you should really think of it as "followed by n ones", since setting those bits obtains the true maximum value due to the carry-over. – EntangledLoops Mar 15 '15 at 21:27
1

@snd: 2^n truly has as its binary representation a "one followed by n zeros". Thus 2^n requires n+1 bits. However 2^n - 1 only requires n bits. Are we in some disagreement about this? – hardmath Mar 15 '15 at 21:51
@hardmath No disagreement, I misread you entirely. You are correct on all counts! Apologies for wasting time, coding all night and overtired. – EntangledLoops Mar 15 '15 at 22:17

score 4 · Answer 4 · answered Sep 13 '13 at 15:34

4

It's worth noting that the base of the positional system doesn't matter. Whatever formula you come up with for the decimal multiplication will work for the binary multiplication.

Let's apply a bit of deduction and multiply two numbers that have relatively prime numbers of digits: 2 and 3 digits, respectively.

Smallest possible numbers:

10 * 100 = 1000 has 4 digits
Largest possible numbers:

99 * 999 = 98901 has 5 digits

So, for a multiplication of n-digit by m-digit number, we deduce that the upper and lower limits are n+m and n+m-1 digits, respectively. Let's make sure it holds for binary as well:

10 * 100 = 1000 has 4 digits
11 * 111 = 10101 has 5 digits

So, it does hold for binary, and we can expect it to hold for any base.

answered Sep 13 '13 at 15:34

Kuba hasn't forgotten Monica

95,931
16
151
313

Are you aware of a proof for this? – phoenixdown Sep 30 '16 at 21:58
1

Such awareness belongs on math stackexchange :) – Kuba hasn't forgotten Monica Oct 02 '16 at 14:21
What made you choose relatively prime bit-widths, 2 and 3, as opposed to non-coprime bit-widths like 2 and 4? – phoenixdown Oct 03 '16 at 16:51
Seemed like a safer choice :) – Kuba hasn't forgotten Monica Oct 03 '16 at 17:59

score 3 · Answer 5 · answered Sep 13 '13 at 15:28

3

x has n binary digits means that 2^(n-1) <= x < 2^n, also assume that y has m binary digits. That means:

2^(m+n-2)<=x*y<2^(m+n)

So x*y can have m+n-1 or m+n digits. It easy to construct examples where both cases are possible:

m+n-1: 2*2 has 3 binary digits (m = n = 2)
m+n: 7*7=49=(binary)110001 has 6 binary digits and m = n = 3

answered Sep 13 '13 at 15:28

Vladimir

170,431
36
387
313

IIRC it gets a little hairy if you're dealing with 2s complement signed. (But it's been 30 years since I mucked with this stuff.) – Hot Licks Sep 13 '13 at 15:31
why does m+n-2 imply it can have m+n-1 digits? – Sep 26 '17 at 22:39
Like I mentioned in the beginning - number of digits is defined by between what powers of two the number lies. You can see for example - 2^3 > 5 >= 2^2, so 5 has 3 digits in binary representation (101) – Vladimir Sep 27 '17 at 04:23

if two n bit numbers are multiplied then the result will be maximum how bit long

5 Answers5