Proof: number of bits in the product of two binary numbers.

Question

Related question on StackOverflow without any proof/intuition.

We have two numbers in binary: one with $n$ digits and another with $m$ digits. I know the general algorithm for multiplying two numbers together by longhand and understand why it works.

What I don't understand is how I can prove that the number of digits in such a product is in the range $[max(m,n), m+n]$.

Any help is greatly appreciated.

Answer 1

You can do better than that: the product of two such positive integers will have either $m+n-1$ or $m+n$ binary digits. And it is not restricted to binary: the equivalent statement is true in other bases including decimal

Hint:

• A positive integer has $n$ base-$b$ digits and most significant digit non-zero if and only if it is in the interval $[b^{n-1},b^{n}-1]$

• $b^{m-1}\times b ^{n-1} = b^{m+n-2}$

• $(b^{m}-1) \times (b^{n}-1) \lt b^{m+n}$