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+d2bd1bd2+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

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

One thought on “How many digits in a product?”

Leave a Reply to Ian Qvist Cancel reply

Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend tohtml.com.

You may subscribe to this blog by email.