Dynamic Java integer/long overflow checking versus performance

This is a rather theoretical question, so while the language is specifically Java, any general solution will suffice.

Suppose I wanted to write a trivial factorial function:

long factorial(int n)
{
    //handle special cases like negatives, etc.

    long p = 1;
    for(int i = 1; i <= n; i++)
    {
        p = p * n;
    }
    return p;
}

But now, I also want to check if the factorial overflows (without simply hard coding a MAX_FACTORIAL_PARAMETER or something of the like). In general checking for overflow during multiplication is as simple as checking the result against the original inputs, but in this case, since overflow can occur at any point, it would be rather expensive to perform more divisions and comparisons in every single loop.

The question then, is twofold--is there any way to solve the factorial problem 开发者_Go百科of overflow without checking for multiplication overflow at every step or hard coding a maximum allowed parameter?

And in general, how should I approach problems that involve many stages of iteration/recursion that could silently fail at every stage without compromising performance by introducing expensive checks at each?

While Java does not help you with this, there certainly are languages that help with overflow. For example, C# provides the checked keyword. Underneath, this feature probably uses hardware support in the form of the overflow flag.

It depends on your specific problem. Maybe you can do curve sketching or some other mathematical analytic.

In your given example it would be the best just to check at every loop. Its not that time consuming, as it won't even modify your complexity class (because O(n) = O(n+n) = O(2n) = O(n)). In most cases it would also be the best thing to do a simple check, as it keeps your code clean and maintainable.

In this specific case the simplest thing to do is hard code the maximum 'n' value. If speed was important to you, you would store all possible values in an array (there aren't many) and not calculate anything. ;)

If you want to improve the method use long result (not much better but a simple change) or use BigInteger which doesn't have an overflow problem. ;)

Is there any way to solve the factorial problem of overflow without checking for multiplication overflow at every step or hard coding a maximum allowed parameter?

No.

And in general, how should I approach problems that involve many stages of iteration/recursion that could silently fail at every stage without compromising performance by introducing expensive checks at each?

I don't think that you can in Java.

Some machine instruction sets set an 'oveflow' bit if the previous integer arithmetic operation overflowed, but most programming languages don't provide a way to make use of it. C# is an exception, as is (IIRC) Ada.

Since Java 8, Java has the Math.multiplyExact() method. This checks internally for an overflow. Since the method is an 'intrinsic' (see here for a list), the Java implementation will be replaced by dedicated low level machine instructions if possible, possibly just checking a CPU overflow flag, thus making the check quite fast.

Btw, note that this seems to be much faster on JDK 1.8.0_40 compared to JDK 1.0.8_05.

In Java, overflow should give you a negative result so you could probably use that as a check:

long factorial(int n)
{
    //handle special cases like negatives, etc.

    long p = 1;
    for(int i = 1; i <= n; i++)
    {
        p = p * n;
    }

    if (p < 0)
    {
        throw new ArithmeticException("factorial: Overflow");
    }

    return p;
}

Alternatively, for languages with positive overflow, since n! > (n - 1)! you could try:

long factorial(int n)
{
    //handle special cases like negatives, etc.

    if (n == 1 || n == 2) { return n; }

    // Calculate (n-1)!
    long p = 2;
    for(int i = 3; i < n; i++)  // Note changes to loop start and end.
    {
        p = p * n;
    }

    long previous = p;  // (n-1)!

    p = p * n;  // Calculate n!

    if (p < previous)
    {
        throw new ArithmeticException("factorial: Overflow");
    }
    return p;
}

Those methods only require one check per factorial.