Search code examples
computer-sciencebit

Mulitplying bits

My textbook says this:

enter image description here

I don’t get this quote in the multiplication section:

The first observation is that the number of digits in the product is considerably larger than the number in either the multiplicand or the multiplier. In fact, if we ignore the sign bits, the length of the multiplication of an n-bit multiplicand and an m-bit multiplier is a product that is n + m bits long. That is, n + m bits are required to represent all possible products.

I see 7 digits in the product but this quote implies there should be 8

Solution

  • The quote is talking about the space required to store the product (bold emphasis mine):

    That is, n + m bits are required to represent all possible products.

    You are only looking at one product. You need to look at all possible products of an n-digit an and m-digit number. For example, for m = n = 4 and in base 10:

    9999×9999 = 99980001

    It should be obvious that this is the maximum size and not the size for every single product because otherwise the product of any n-digit number and 0 should have n+1 digits when it obviously only has 1 digit.