Search code examples
javacomputer-science

Is there an algorithm to compute if a calculation will overflow a type size?


Is there an algorithm which can be applied to most languages to determine if a calculation when preformed will overflow the type size?

As an example if given the following code fragment in Java (although again I am looking for a general approach in any language)

long variable = 2;
while(true){
    variable = variable * Generalclass.function();
}

assuming that Generalclass.function() will return something which causes variable to increase eventually variable will overflow, so how can it be determined if this call has caused this to happen if Generalclass.function()'s properties are unknown (properties other than increasing the value of variable). Note that variable is declared as a long so simply checking against a larger data type will not work since no such data type exists.


Solution

  • The most direct answer to your question is "no, there isn't an algorithm to compute if a calculation will overflow". Each type of operation (add, mult, etc.) has unique requirements for detecting overflow conditions. At the machine language level, some processors have special condition codes which can be checked if an arithmetic operation overflowed, but when coding at a higher level, you don't have access to this.

    Check out the book, "Hacker's Delight" for some algorithms for detecting overflow. You might also want to look at the source code for the various Java Math "exact" methods. Some of the implementations refer to Hacker's Delight, and many of them also have "intrinsic" versions which are replaced with low-level alternative implementations which are faster.