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?

Pottage

Didnt ever tried similar project, so only got quesions: whats the point in knowing about overflow beforehand? Optimization for smaller nmbers to be quick, or something less obvious? U need an exact solution, or accept one that might give false overflow alarms? – Perlie

Your question and your comment in response to one of the answers say that you're using signed operands, but the title says unsigned. Which is it? Unsigned arithmetic is probably easier to deal with, and is probably more suitable for working with arbitrary precision numbers. – Provincial

I will be doing signed arbitrary calculations using unsigned primitive types as the base components, as in an array of unsigned 64 bit longs that represent the base – Pottage

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

Billow

Because that's how you might cause overflow. If that does indeed occurs, it means one of your numbers is already big. – Amanita

Answer 2

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).

Loggins

Your example is only true in the case of unsigned operands, it doesn't hold in the general case. – Coupling

And the behavior of signed overflow is undefined. – Provincial

@Keith: For primitive types, of course. The OP is talking about implementing an arbitrary-precision type. He needs to be able to handle overflow to grow the representation (and so prevent overflow!). – Coupling

@OliCharlesworth: I think he was asking about overflow in primitive types used in the implementation. For example, if an array of 64-bit numbers represents a 6400-bit number, I assume he was asking about 64-bit overflow. Jarrod, can you clarify? – Provincial

Once you take underflow into account, this method no longer works. =| – Amanita

@OliCharlesworth: Two things to note: first, when working with arbitrary precision numbers, one usually stores an unsigned magnitude and a sign separately. Thus, you usually only need to be able to detect unsigned overflows. Second, and more importantly, the processor detects signed overflow/underflow just as easily as it does unsigned overflow. There isn't a tidy portable way to get at the flags that are set, but it is possible to do on any sane platform -- that's the correct way to approach this task. – Loggins