Overflow and range checking for mul/div

I'm currently trying to implement range checking and overflow/underflow checking for multiplication and division, but... it's more complicated than addition and subtraction.

My current way is somewhat messy.
If we assume that a custom range is set to:
Min: 0
Max: 100 000

And we have the number 15 and want to multiply by 10 000, we would get 150 000, which is above > 100 000 and thus would result in overflow and a number that is 50 000 afterwards.
The problem is that checking if Result > upper bound is not always feasible, since for example, if the upper bound is the maximum range for a 64-bit integer. The result would be an overflow, so I can't do it that way. This suggests another way.
Using mathematics, I came up with:

Min: 0
Max: 100 000
Base: 15
Multiply By: 10 000

100 000 / 15 = 6666
(Divide upper range with the current number stored (m_Data). Basically see how many times we can multiply this number with until we hit the upper bound. Also truncate to integer.)

6666 >= 10 000
(Check if the number we can multiply with is larger or equal to the amount we want to multiply with. If the result is true, then we will have no overflow.)
If true, no overflow

(If no)
10 000 - 6666 = 3334
(Get the remaining amount to multiply with that would exceed the upper bound.)
15 * 6666 = 99 990
(Multiply the current number with the maximum number we can multiply by that does not exceed the upper bound.)
100 000 - 99 990 = 10
(Calculate the difference between the maximum number and the result of the current operation. This is to take into account the lost digits due to the integer truncation.)
15 * 3334 = 50 010
(Multiply the number by the amount that exceeded the upper bound.)
50 010 - 10 = 50 000
(Subtract the difference due to the integer truncation.)

Since floating point numbers aren't reliable, I chose to do integer math instead.
But this is a pretty long way of doing it and it doesn't even take into account negative numbers on either side!
There must a better way to do it (big precision library to handle bigger numbers?) or a way to modify the algorithm or whatever to call it to work with negative numbers.

This is only for multiplication, as well. Then I'd have to implement a similar method for division. So I'm looking for insight into the matter.
Anything that might help would be nice.

Um... I didn't give this a lot of thought, but I don't think it will work. If the values more than double the maximum this will not work.

Also, the entire operation looks like an attempt to reproduce '%' without using '%'.

Soma

Code:

---

unsigned long maximum(100000);
unsigned long value(15);
unsigned long multiple(10000);
unsigned long overflow(multiple - (maximum / value));
unsigned long remainder(maximum % value);
unsigned long result((overflow * value) - remainder);

---

I'm not too familiar with assembly, but isn't there an assembly instruction (at least on x86) that can tell you if there was an overflow in the previous operation?
If so, that would help with the case of integer overflow.

- Will your "custom ranges" always be within the range of an available integer type?
- Do you want to stick to integers?

--
Computer Programming: An Introduction for the Scientifically Inclined

Quote:

---

Originally Posted by cpjust

I'm not too familiar with assembly, but isn't there an assembly instruction (at least on x86) that can tell you if there was an overflow in the previous operation?
If so, that would help with the case of integer overflow.

---

Sure, but that would require writing the math in assembler too, because the overflow flag is transient - it doesn't remain set if you do any other math operation (e.g. the compiler does some math to calculate the address of, say, a member variable). So you need to pair the calculation itself with a jump on overflow (or interrupt on overflow, but that's a bit excessive, I think).

And of course, that only applies if you overflow the actual hardware value. So if the calculation is artificially bounded (e.g 100000), then overflow flag in the processor won't work.

--
Mats

Quote:

---

Originally Posted by phantomotap

Also, the entire operation looks like an attempt to reproduce '%' without using '%'.

---

My bad. I forgot all about it.

Quote:

---

Originally Posted by cpjust

I'm not too familiar with assembly, but isn't there an assembly instruction (at least on x86) that can tell you if there was an overflow in the previous operation?
If so, that would help with the case of integer overflow.

---

Yes, as mats explained, it doesn't seem very feasible.

Quote:

---

Originally Posted by Sander

- Will your "custom ranges" always be within the range of an available integer type?
- Do you want to stick to integers?

---

Currently I'm sticking with integers, native built-in types.
Although, however, since the class is templated, it is actually possible to supply a custom class as a wrapper for custom integers later.

I don't think it will be easy to work out the specifications for your new type. I assume you're trying to make some kind of "wrapper" allowing you to do ordinary math operations, but keep the result within a (custom) range and set an overflow flag upon wrapping around.

But suppose you set a custom range of 10 .. 20 and add 7 to 15. The result would be 22, which is over the specified maximum so you set the overflow flag, but then what do you set the result to? You can't set it to 2 because that would also be out of the range, and yet no other choice makes sense...

Perhaps, but it's better to wrap twice in such case.

Quote:

---

Originally Posted by Sander

I don't think it will be easy to work out the specifications for your new type. I assume you're trying to make some kind of "wrapper" allowing you to do ordinary math operations, but keep the result within a (custom) range and set an overflow flag upon wrapping around.

But suppose you set a custom range of 10 .. 20 and add 7 to 15. The result would be 22, which is over the specified maximum so you set the overflow flag, but then what do you set the result to? You can't set it to 2 because that would also be out of the range, and yet no other choice makes sense...

---

Wouldn't it wrap around to 12 in that case?
Anyways, if it overflowed, what difference does it make what you set the value to? The result is out of range.
What about throwing an exception on underflow/overflow?

Quote:

---

Originally Posted by cpjust

What about throwing an exception on underflow/overflow?

---

That's part of the design too, but I decided to allow you to not throw an exception because exceptions are incredibly slow.
Traits struct:

Code:

---

template<typename T>
struct IntTraits
{
        const static bool bUnderflow = true;
        const static bool bOverflow = true;
        const static bool bThrow = false;
        const static bool bLogging = false;
        const static bool bShiftDataLost = true;
        const static bool bAssert = true;
        const static T RangeUpper = 2; //boost::integer_traits<T>::const_max;
        const static T RangeLower = 1; //boost::integer_traits<T>::const_min;
};

---

Quotients don't overflow. If the quotient would wrap around, then a and b should have wrapped around, meaning that you are dividing numerals in a type too small. I suppose you could downcast the result to a smaller type too, but that would be a construction exception, since you can't fit the number into the range without truncating bits.

The basic principles you need to remember come down to the causes of overflow and underflow (assuming an underflow is producing a result less than allowed minimum, and overflow is producing a value that wraps or exceeds allowed maximum).

Assume we have two positive (non-zero) values a and b that are constrained to in the range [minimum, maximum]. Overflow on multiplication will only occur if a*b exceeds the maximum allowed value. i.e. a*b > maximum. That can only occur if both values are greater than 1 (multiplying a value in range by a value < 1 cannot give overflow). So a test for overflow is "if (a > 1 && b > 1 && a *b > maximum)" which can be recast as "if (a > 1 && b > 1 && a > maximum/b)" [this can be simplified, obviously, if minimum exceeds 1].

It is possible to formulate similar tests for underflow on multiplication or overflow/underflow on division. I'll leave those as an exercise.

The key is remembering basic mathematical relationships between inequality relationships. If a, b and c are all positive, then a test "if (a*b > c)" is the same as "if (a > c/b)".

c = a * b overflows if c / b != a

Integer division cannot produce overflow. Divide by zero is a special case you already have to handle.

Quote:

---

Originally Posted by iMalc

c = a * b overflows if c / b != a

Integer division cannot produce overflow. Divide by zero is a special case you already have to handle.

---

For basic integral types in C/C++ that is true. It is not true for all integral types (eg other languages allow specification of integral types with values in specified ranges, and such things can be implemented as a class in C++).

If your acceptable range is [-10,-1] then overflow on division is possible. -10/-1 equals 10 which exceeds any value in the accepted range.

Quote:

---

Originally Posted by grumpy

It is possible to formulate similar tests for underflow on multiplication or overflow/underflow on division. I'll leave those as an exercise.

The key is remembering basic mathematical relationships between inequality relationships. If a, b and c are all positive, then a test "if (a*b > c)" is the same as "if (a > c/b)".

---

The problem with
(a * b > c) == (a > c / b)
That it would only work when the range was the maximum for the integer can hold. If I specify a custom range, that test will be useless.

Quote:

---

Originally Posted by grumpy

For basic integral types in C/C++ that is true. It is not true for all integral types (eg other languages allow specification of integral types with values in specified ranges, and such things can be implemented as a class in C++).

If your acceptable range is [-10,-1] then overflow on division is possible. -10/-1 equals 10 which exceeds any value in the accepted range.

---

Whoops missed that.
All you have to do then though is check the value of the result. It isn't actually necessary to work out if the end result is in range before performing the calculation in this case.
I guess -32768 / -1 (assuming a 16-bit int) would be a problem but that's the only case.

Quote:

---

Originally Posted by Elysia

The problem with
(a * b > c) == (a > c / b)
That it would only work when the range was the maximum for the integer can hold. If I specify a custom range, that test will be useless.

---

Rubbish. It is basic mathematics.

Quote:

---

Originally Posted by iMalc

Whoops missed that.
All you have to do then though is check the value of the result. It isn't actually necessary to work out if the end result is in range before performing the calculation in this case.
I guess -32768 / -1 (assuming a 16-bit int) would be a problem but that's the only case.

---

That's assuming your type can hold the value it is not intended to represent. By definition, if you have an overflow or underflow situation, it is possible the type cannot represent the value of the result. Your conclusion does not work for types designed or specified to hold particular custom ranges.

Quote:

---

Originally Posted by iMalc

Whoops missed that.
All you have to do then though is check the value of the result. It isn't actually necessary to work out if the end result is in range before performing the calculation in this case.
I guess -32768 / -1 (assuming a 16-bit int) would be a problem but that's the only case.

---

The problem is that if there is an actual overflow or underflow for the type because it cannot represent the actual value, then it's impossible to check the result.
Say, I use uint8_t.
If the result is 256, I get 0 instead. And 0 < integer_max, so by that, I get a valid number.

Quote:

---

Originally Posted by grumpy

Rubbish. It is basic mathematics.

---

My apologies. My thinking was in error. Of course you're right.
But you've given me light. I don't think I'm used in thinking in terms of equations for computer mathematics problems...

However, the question remains: how to wrap the values correctly? If overflow/underflow occurs, the numbers must wrap around the maximum like it does with native integers.
We'd rather not emulate this at bit level.

Quote:

---

Originally Posted by Elysia

The problem is that if there is an actual overflow or underflow for the type because it cannot represent the actual value, then it's impossible to check the result.

---

The trick is to do things to check if an operation would overflow/underflow BEFORE doing the operation. Mathematics is great for finding those things to do.

Quote:

---

Originally Posted by Elysia

My apologies. My thinking was in error. Of course you're right.
But you've given me light. I don't think I'm used in thinking in terms of equations for computer mathematics problems...

---

Mathematics is all about describing a problem in a way that allows it to be solved, and finding alternative but equivalent operations if one method does not work for some reason. That philosophy is quite useful with programming.

Let's say, for sake of discussion, we want to throw an exception if multiplying two positive valued ints causes an overflow (again for sake of discussion, this means "produces a result greater than INT_MAX").

With handling of overflows or underflows, one technique is to do the operation (multiplication, division, etc), check if an overflow/underflow has occurred, and (if it has) decide what to do next (recovery action, etc). The practical problem is that techniques by which overflow/underflow are reported are machine dependent, so the methods of detecting them are too.

To meet our requirement, we could do this;

Code:

---

    /* assume a and b are both > 0 and <= INT_MAX */
    result = a*b;
    if (overflow_detected(result))
      throw OurException;

---

The problem with this is that the techniques of detecting an overflow are machine dependent (particularly as some machines wrap values, so the test is not simply "if (result > INT_MAX)". The techniques for recovery of such a condition are also machine dependent (more so for floating point, but still true for ints, as there is implementation defined behaviour).

Another way is to detect the potential overflow BEFORE doing the operation and, if a positive detection occurs, throw the exception and DO NOT do the computation. Since we are trying to detect a situation where a*b > INT_MAX, we can divide by one of the values. So the technique might be

Code:

---

  /*  assume a and b are both > 0  and <= INT_MAX */
 
  if (INT_MAX/a < b)      /*  overflow would occur if we did multiplication */
        throw OurException;
  result = a*b;

---

This has the same net effect, but no overflow occurs that needs to be recovered from in a machine dependent manner.

Quote:

---

if (INT_MAX/a > b)

---

Shouldn't that be less than?

The obvious problem of early detection is the overhead. In the example above, an integer division is needed in addition to the integer multiplication, solely for the purpose of checking for overflow. Division is considerably slower than multiplication, so you slow down the operation a lot.
Checking the overflow flag, on the other hand, incurs merely the penalty of a conditional jump.

Well, guess I'll just have to suffice for aborting the operation if an overflow/underflow is detected. This is becoming non-portable and too complex.
EDIT:
There's a problem with:

m_Data < Traits<T>::RangeLower / Data.m_Data
m_Data * Data.m_Data < Traits<T>::RangeLower

They will always equal each other for all numbers but 0.
If we define m_Data = 2 and Data.m_Data = -2, then
In the first, the equation will be 2 < 0 / -2 = 2 < 0 (FALSE)
And the second will be 2 * -2 < 0 = -4 < 0 (TRUE)
So they will not match and this causes a problem.

Although, as for detection, a small overhead may be necessary. However, I have given the option not to check for overflow/underflow, which gets rid of that overhead entirely.
But fast overflow/underflow checking would be a good thing.

Quote:

---

Originally Posted by Elysia

They will always equal each other for all numbers but 0.
If we define m_Data = 2 and Data.m_Data = -2, then
In the first, the equation will be 2 < 0 / -2 = 2 < 0 (FALSE)
And the second will be 2 * -2 < 0 = -4 < 0 (TRUE)
So they will not match and this causes a problem.

---

This has nothing to do with zero and everything to do with negative numbers. Recall that when you multiply or divide an inequality by a negative number, the inequality reverses. So in this case you multiply your inequality by Data.m_Data (to get it out of the denominator on the right). Since you multiply by a negative number, the inequality reverses. (Try it with 1 in place of the zero and see what happens.)

Quote:

---

Originally Posted by CornedBee

Shouldn't that be less than?

---

Yep; I typed too fast. Will fix in a tic.

Quote:

---

Originally Posted by CornedBee

The obvious problem of early detection is the overhead.

---

True. Usually, the better approach is a design that ensures the overflow will not occur. If a condition is prevented, no need to detect it before or after. Analysis of specific cases allows that, although it's difficult in general (eg for arbitrary input).

Checking the overflow flag only works on some systems. On some processors, a system exception is generated on overflow. Recovery from those suckers is non-trivial.

Quote:

---

Originally Posted by tabstop

This has nothing to do with zero and everything to do with negative numbers. Recall that when you multiply or divide an inequality by a negative number, the inequality reverses. So in this case you multiply your inequality by Data.m_Data (to get it out of the denominator on the right). Since you multiply by a negative number, the inequality reverses. (Try it with 1 in place of the zero and see what happens.)

---

I get what you say (although you sure put it in difficult words), but sign changes does not work. Unless you magically can make the following equation work with a sign change:

2 * -2 < -1 (TRUE)
2 < -1 / -2 (FALSE)
2 < 1 / -2 (FALSE)
2 < -1 / 2 (FALSE)
2 < -1 * -2 (FALSE)
2 < 1 * -2 (FALSE)
2 < -1 * 2 (FALSE)

What does the books say about this? I don't remember. It confuses me, as well.

Quote:

---

Originally Posted by Elysia

I get what you say (although you sure put it in difficult words), but sign changes does not work. Unless you magically can make the following equation work with a sign change:

2 * -2 < -1 (TRUE)
2 > -1 / -2 (TRUE)

---

Fixed.
Reverse means to go the other way -- multiplying or dividing a negative number changes < to > and back around. (E.g. -2x < 8 --> x > 4. You divided by a -2, so the inequality reverses.)

The other things you have listed bear no relation to the first one you started with.

Now we're talking! :D
So long since I did math with > and <. Especially with negative numbers.

Quote:

---

Originally Posted by grumpy

That's assuming your type can hold the value it is not intended to represent. By definition, if you have an overflow or underflow situation, it is possible the type cannot represent the value of the result. Your conclusion does not work for types designed or specified to hold particular custom ranges.

---

Well that's just it, I am assuming that the data types he is using to represent all this are plaing old ints, chars, shorts, __inst64s etc. As long as the variable holding the result type is the same size then the division wont overflow, except in the case I gave, and you can perform the range check afterwards. From the point of view of his implementation, it will work, that's what I'm trying to say.
I'm only talking about the division case here of course.

Quote:

---

Originally Posted by iMalc

Well that's just it, I am assuming that the data types he is using to represent all this are plaing old ints, chars, shorts, __inst64s etc. As long as the variable holding the result type is the same size then the division wont overflow, except in the case I gave, and you can perform the range check afterwards. From the point of view of his implementation, it will work, that's what I'm trying to say.
I'm only talking about the division case here of course.

---

Unless, of course, the number was a floating number...
But if it's an integer, I can relate to that you're right... A possible optimization!