# Multiplication Overflow

### Problem

A commonly overlooked problem with C integral types is multiplication and what happens if the result overflows.

There is useful a StackExchange article on multiplication of large numbers, how to catch overflow.

The nub of the issue is this. Let's take an 8 bit machine and two unsigned numbers and do some maths:

uint8_t n1 = 129; uint8_t n2 = 129; uint8_t r = n1 * n2;

What do we know about the result, `r`? Answer, nothing. It can't be 16641 (the result of 129 * 129) as that is too big for the 8 bit integral type. Could it be 1 (16641 modulo 256)? Well, it *could* be but as the number overflowed we can't rely on anything about `r`.

Not only is the result undefined but **we don't even know that the result overflowed** and is undefined!

#### Solution

Can we do anything about it? Yes we can but suddenly everything is hard.

Essentially, we need to pre-test that the result will not overflow before we perform the multiplication. How can we do a pre-test without overflowing in the pre-test? Well, what we want of the pre-test is to answer the question: is the result of the multiplication going to be bigger than our maximum value, i.e. is `n1 * n2 > UINT8_MAX` true?

We can do some trivial rewrite of that (divide both sides by `n2`) to get the question: is `n1 > UINT8_MAX / n2` true? Division doesn't overflow (other than if `n2` is zero, of course) so now we have a "quick" test to see if the projected multiplication will overflow.

Integral division isn't very quick and so we're trading risky for slow (as we now have to do a division, a comparison and the multiplication as a minimum).

#### Carry

If you want to go ahead and multiply anyway to compute the carry then the StackExchange page lists a few variations on the theme: chop the arguments up into half-words (4 bits in our case!) but use full-word objects for them, perform long multiplication of the four (half-word) segments watching for overflow into the top half of the word and keeping track of the carry. Mash all the parts together at the end.

Easy!

### Repercussions

Now we know what to do this means that **every** occurrence of integral multiplication in your code must be managed for the case where it could overflow the result type.

*Groan!*

Document Actions