How to determine before hand if an unsigned calculation can overflow?

Question

As a personal project, I am working on introducing a type of arbitrary precision number for my favorite project.

I already know about all the popular, trusted and reliable libraries that do this. I want to work on a solution as a self-improvement project.

I am researching an area and trying to figure out if there is a way to roughly predict if the operation will cause an overflow before I actually do the calculations. I'm also not so worried about false positives.

I want to be able to use the minimum space suitable for calculation. If the calculation remains within its native boundaries, I will save it there.

For example: Multiplying two 64 bit Integers if each are large enough will cause an overflow. I want to define this and convert the numbers to my number only if the result can exceed 64 bits of resolution. I will work with signed numbers in this experiment.

What is the most efficient and effective way to detect overflow / underload?

Answer 1

Take only the most significant bit in both numbers, shift left by one, if the result (for example: multiplying) of these numbers causes an overflow, you have a good chance of overflow.

Although not accurate, it is incredibly fast and a good indicator that you need a larger data type for the result.

This can only make sense for large data types, for which the operator is expensive, for simple things (even for 64-bit numbers), I think you can rely on the built-in CPU arithmetic .. see this question: Undefined when exceeds 64 bit

Answer 2

There John Regehr paper about it.

Answer 3

It is almost always easier (and often faster) to do naive calculations and find out if an overflow has occurred. Is there a specific reason why you would like to discover an opportunity before calculating?

It is usually fairly easy to detect if an overflow has occurred after the calculation has completed. Since naive operations are cheap, it also does not bring much cost to the computation if there is an overflow, even if you need to redo some work. (Usually, however, you do not even need to do this).

Here's a (very) simple example: if I add two unsigned 64-bit numbers, I can check the overflow by comparing the sum with any of the additives - if it is less than the overflow. Thus, overflow detection after computation requires only one comparison (very cheap).