How to determine before hand if an unsigned calculation may possibly overflow?

Question

As a personal project I am working on implementing an Arbitrary Precision number type for a pet project of mine.

I already know about all the popular, tested and robust libraries out there that do this. I want to work on a solution as a self improvement education project.

I am researching the area and trying to figure out if there is some way to roughly predict if an operation will cause an overflow before I actually do the calculations. I am not so concerned about false positives either.

I want to be able to use the smallest space that is appropriate for the calculation. If the calculation will stay within its native bounds I keep it there.

For example: Multiplying two 64 bit Integers if each are large enough will cause an overflow. I want to detect this and up-convert the numbers to my number type only if the result may exceed 64 bits of resolution. I will be working with signed numbers in this experiment.

What is the most sane, efficient way to detect an overflow/underflow?

Answer 1

Take only the highest bit in both numbers, shift left by one, if the result (eg: multiplication) of those numbers would cause an overflow, you have a good chance for an overflow.

Though it's not precise, it's blazingly fast and a good indicator that you need a larger data type for the result.

This might only make sense for large data types for which the operator is costly, for simple things (even for 64bit numbers), I think you can rely on the CPU's builtin arithmetic.. see this question: Undefined behavior when exceed 64 bits

Answer 2

There's John Regehr's paper about that.

Answer 3

It is almost always easier (and often faster) to do the naive computation, and detect if overflow occurred. Is there a specific reason why you would like to detect the possibility before doing the computation?

It is generally quite easy to detect if an overflow occurred once the computation is finished. Because naive operations are cheap, this also doesn't add much to the cost of your computation if an overflow did occur, even if you end up needing to redo some work. (Usually, however, you won't even need to do that).

Here's a (very) simple example: if I add two unsigned 64-bit numbers, I can check for overflow by comparing the sum to either of the addends -- if it is smaller, than overflow occurred. Thus, detecting overflow after the computation requires only a single comparison (very cheap indeed).