, 2 min read
How many digits in a product?
We often represent integers with digits. E.g., the integer 1234 has 4 digits. By extension, we use ‘binary’ digits, called bits, within computers. Thus the integer 7 requires three bits: 0b111.
If I have two integers that use 3 digits, say, how many digits will their product have?
Mathematically, we might count the number of digits of an integer using the formula ceil(log(x+1)) where the log is the in the base you are interested in. In base 10, the integers with three digits go from 100 to 999, or from 102 to 103-1, inclusively. For example, to compute the number of digits in base 10, you might use the following Python expression ceil(log10(x+1)). More generally, an integer has d digits in base b if it is between bd-1 and bd-1, inclusively. By convention, the integer 0 has no digit in this model.
The product between an integer having d1 digits and integer having d2 digits is between bd1+d2-2 and bd1+d2–bd1–bd2+1 (inclusively). Thus the product has either d1+d2-1 digits or d1+d2 digits.
To illustrate, let us consider the product between two integers having three digits. In base 10, the smallest product is 100 times 100 or 10,000, so it requires 5 digits. The largest product is 999 times 999 or 998,001 so 6 digits.
Thus if you multiply a 32-bit number with another 32-bit number, you get a number than has at most 64 binary digits. The maximum value will be 264 – 233 + 1.
It seems slightly counter-intuitive that the product of two 32-bit numbers does not span the full range of 64-bit numbers because it cannot exceed 264 – 233 + 1. A related observation is that any given product may have several possible pairs of 32-bit numbers. For example, the product 4 can be achieved by the multiplication of 1 with 4 or the multiplication of 2 times 2. Furthermore, many other 64-bit values may not be produced from two 32-bit values: e.g., any prime number larger or equal than 232 and smaller than 264 .
Further reading: Computing the number of digits of an integer even faster