Thread: Overflow and range checking for mul/div

  1. #1
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654

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

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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);

  3. #3
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    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.

  4. #4
    Registered User
    Join Date
    May 2008
    Posts
    53
    - 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

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by cpjust View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by phantomotap View Post
    Also, the entire operation looks like an attempt to reproduce '%' without using '%'.
    My bad. I forgot all about it.

    Quote Originally Posted by cpjust View Post
    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 View Post
    - 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.
    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.

  7. #7
    Registered User
    Join Date
    May 2008
    Posts
    53
    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...

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Perhaps, but it's better to wrap twice in such case.
    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.

  9. #9
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by Sander View Post
    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?

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by cpjust View Post
    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;
    };
    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. #11
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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.

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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)".
    Last edited by grumpy; 06-05-2008 at 05:45 PM.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    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. #14
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by iMalc View Post
    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.

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by grumpy View Post
    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 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.

Popular pages Recent additions subscribe to a feed