Computers Cannot Multiply

Published: 2024-09-18

What would you call a function that is incorrect 99.999999% of the time? Broken?

Let’s take a look: what happens if you multiply two (unsigned) 4-bit numbers?

• All numbers multiplied by zero or one are okay.
• If we multiply by 2, half the numbers are incorrect.
• If we multiply by 3, two-thirds of the numbers are incorrect.
• If we multiply by 4, three-quarters of the numbers are incorrect.
• etc

So for four-bit numbers, out of 256 possible combinations, 180 results are incorrect, and 76 results are correct. This makes the result incorrect about 70% of the time.

But: it gets much, much worse the more bits your numbers have. The possible value space increases dramatically, but the same results as above apply: when multiplying by two, half are incorrect, etc, etc. This means that when we use longer numbers, there are more incorrect results:

Thus, 32-bit multiplication is incorrect 99.999999% of the time.

The next fun thing to consider is why computers seem to be able to multiply, despite not being able to.