• How can I detect Int overflow?

    From bertsierra@gmail.com@21:1/5 to Alex Mentis on Thu May 18 17:59:18 2017
    On Saturday, September 4, 2010 at 5:41:13 AM UTC-7, Alex Mentis wrote:
    How can I check that the calculation "place * 10 + digitToInt c" is
    within the bounds of Int before outputting it and report an error otherwise?

    Sorry to arrive to this thread a bit 'late'. Several folks have suggested excellent workarounds to use internally during conversion to avoid arithmetic overflow, or to properly detect/report it if it does. The arbitrary-precision Integer data type
    seems most reasonable -- just perform the conversion until any intermediate value falls outside of the range [minBound::Int..maxBound::Int], and handle the error or exception yourself if it does. Or you can make temporary use of a SafeInt (see Data.
    SafeInt) during this calculation if you prefer, since that bound checking will be automatic and you won't need to do it yourself.

    I do a lot of work in C with combinatoric functions which can blow up quite easily. Often even if a closed form equation for the number of solutions or cases can be expressed, it can easily exceed any fixed-with integer representation. I use C to get
    the best bang-for-buck in terms of execution time, but there you don't have any ability to turn on a compile-time flag to check all arithmetic for overflow (unlike Swift or C# or more modern derivatives of C).

    But there is a DIY solution if you don't mind working with a few algebraic inequalities of integer variables. You'll see that you can always unroll your expression to produce a safe arithmetic expression to show when overflow would (or would not) occur.

    Given your expression, this could be done in two steps. First, I will assume that place>=0 is always true. Given that, the first goal is to make sure that place*10 <= maxBound::Int. So we need only to make sure that place <= maxBound::Int `div` 10 (
    where 'div' refers to the integer division operator). If place falls above that value, you have successfully detected the overflow in advance. Next, with the new value of place known to be safe, you merely need to make certain that digitToInt c <=
    maxBound::Int - place*10.

    This could also be done in a single step: Since we know that 'digitToInt c' must fall in the range [0..9], a more efficient solution would be to simply make sure that the following expression holds True, and if place falls above this bound and the
    expression is False, the arithmetic overflow would have been detected in advance. This is simply the original inequality solved for place to find its maximum value:

    place <= (maxBound::Int - digitToInt c) `div` 10

    You also need to handle the case that negative numbers can go one value lower, since (abs minBound::Int) > (abs maxBound::Int), but with a bit of thought you can handle this via similar means.

    While I find myself doing this quite routinely in C working in combinatorics where speed is paramount and you want to restrict the overflow checking to where you know it might occur (in a fully debugged program, that is), this isn't the best way to go in
    your case.

    You have excellent language capabilities in Haskell like Integer or SafeInt types which you can use internally during conversion to prevent overflow and an incorrect result. Your code will also be far more readable than what I showed. However, whenever
    you find the need for speed and you're working in a language that doesn't offer alternatives easily (other than binding in multiprecision integer libraries), the algebraic approach is good to keep in your toolkit for when it is needed.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)