Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Not sure if many of you speak binary, but the question is to prove that 2n bits are sufficient to store the product of two unsigned n-bit numbers (i.e., there will be no overflow).

I've thought of a simple method by contradiction, but its way too simple and I feel theres something wrong with it. So here it is:

Suppose not, that is, suppose that 2n bits are not sufficient to store the product of two unsigned n-bit numbers.

Then consider the product of two binary numbers 1111 x 1111. The result is 11100001, which is 8 bits=2n where n=4. So 2n was indeed sufficient to hold the product.

Have we proved anything here? Is this legit. If not, what are some ways I could prove this?

share|improve this question
1  
I think a direct proof would be more suitable. But then again, that would be in contradiction with your title. –  Myself Mar 9 '11 at 17:14
1  
You proved one thing, that the assumption (2n bits are not sufficient) was false in this one case –  user1708 Mar 9 '11 at 17:15

2 Answers 2

up vote 4 down vote accepted

Your mistake is negating (for every $n$ bit numbers $a,b$ the product $ab$ is a $2n$ bit number or less) to (for every $n$ bit numbers $a,b$ the product $ab$ takes more than $2n$ bits) (which you did contradict with your example) but the actual negation is (for some $n$ bit numbers $a,b$ the product $ab$ takes more than $2n$ bits). You can't contradict a "for some" just by giving an example though.

As for proving the theorem, you could prove the lemma if $x \le y$ then $x$ takes less than or equal to the number of bits that $y$ takes. Then 1111x1111 = 11100001 does prove the theorem in the case of n=4, but you will have to do this multiplication in a general way to prove it for every n.

Another useful thing to make proving this easier is that 2^n-1 = 1111111...111 for n 1's.

share|improve this answer
    
So how that that change for $(2n-1)^2$, how many 1's would that be? –  maq Mar 9 '11 at 17:33
    
did you mean $(2^n-1)^2$? That is $2^{2n}-2^n+1$ which is less than or equal to $2^{2n}-1$ and by the lemma this takes at most $2n$ bits. –  quanta Mar 9 '11 at 18:43

Your proof isn't valid - maybe there are some other numbers that do require more than $2n$ digits? You only provide a specific example which doesn't. This way you can prove that the product requires only $1$ digit - consider $0 \times 0$.

Your idea actually works, but there's no need for proof by contradiction. For the case $n=4$, each of the $n$-bit numbers is at most $15$, and so the product is at most $225$, which requires only $2n=8$ bits. This generalizes.

share|improve this answer
    
So how would I use this general fact? I mean I could keep providing examples, but how could I generalize this in terms of n? –  maq Mar 9 '11 at 17:18
    
To generalize the example, the largest product you can get from $n$-digit numbers is from $(2^{n+1} - 1)^2$. How many bits does that take? –  Mitch Mar 9 '11 at 17:22
    
Actually I got up to that part, but I couldnt figure out how many bits could represent that number. –  maq Mar 9 '11 at 17:23
    
@mohabitar: If you expand $(2^{n+1}-1)^2$ you get $2^{\rm something} - {\rm something else}$ which is less than...quanta spells it out for you. (I think the lemma is unnecessary but that's debatable) –  Mitch Mar 9 '11 at 18:56

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.