Overflow and range checking for mul/div

This is a discussion on Overflow and range checking for mul/div within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by grumpy For basic integral types in C/C++ that is true. It is not true for all integral ...

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by grumpy View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #17
    Registered User
    Join Date
    Jun 2005
    Posts
    6,283
    Quote Originally Posted by Elysia View Post
    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.

  3. #18
    Registered User
    Join Date
    Jun 2005
    Posts
    6,283
    Quote Originally Posted by iMalc View Post
    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.

  4. #19
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,583
    Quote Originally Posted by iMalc View Post
    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 View Post
    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.
    Last edited by Elysia; 06-06-2008 at 06:14 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #20
    Registered User
    Join Date
    Jun 2005
    Posts
    6,283
    Quote Originally Posted by Elysia View Post
    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 View Post
    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.
    Last edited by grumpy; 06-06-2008 at 07:07 AM. Reason: Fixed inequality in "INT_MAX/a < b" is response to CornedBee's post below

  6. #21
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #22
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,583
    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.
    Last edited by Elysia; 06-06-2008 at 07:03 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #23
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Elysia View Post

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

  9. #24
    Registered User
    Join Date
    Jun 2005
    Posts
    6,283
    Quote Originally Posted by CornedBee View Post
    Shouldn't that be less than?
    Yep; I typed too fast. Will fix in a tic.
    Quote Originally Posted by CornedBee View Post
    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.
    Last edited by grumpy; 06-06-2008 at 07:08 AM.

  10. #25
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,583
    Quote Originally Posted by tabstop View Post
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #26
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Elysia View Post
    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.

  12. #27
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,583
    Now we're talking!
    So long since I did math with > and <. Especially with negative numbers.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #28
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by grumpy View Post
    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.
    Last edited by iMalc; 06-06-2008 at 02:08 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #29
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,583
    Quote Originally Posted by iMalc View Post
    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!
    Last edited by Elysia; 06-06-2008 at 02:12 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21