Saturated arithmetic For project Euler, I need quite often to test things like is x*y*z &lt; 1e18. Since BigInteger is usually too slow, long overflows, and double may return incorrect result due to rounding, I wanted to use long with appropriate checks. As Guava's LongMath.checkedMultiply throws, it can't be used as exception handling is too slow, too. So I decided to write a saturated arithmetic class.

As usual, feel free to ignore my slightly deviating coding conventions. The code has been optimized, so it's a bit hacky. There should be no bugs as it's thoroughly tested. Simplifications and optimizations are most welcome.

@UtilityClass public class SaturatedMath {
    public static long pow(long base, int exp) {
        if (exp==0) return 1;
        checkArgument(exp&gt;=0);

        // Handle small bases and also Long.MIN_VALUE
        if (Math.abs(base) &lt;= 2) return powSpecial(base, exp);

        switch (exp) {
            case 1: return base;
            case 2: return square(base);
            case 3: return cube(base);
        }

        // Now base is at least 3, so the exponent can't be big.
        if (exp &gt;= FLOOR_ROOTS_MAX_LONG.length) return saturate(base &lt; 0 &amp;&amp; (exp&amp;1) != 0);

        final long limit = FLOOR_ROOTS_MAX_LONG[exp];
        if (base &gt; +limit) return Long.MAX_VALUE;
        if (base &lt; -limit) return saturate((exp&amp;1) != 0);

        // No more overflow.
        return powUnsaturated(base, exp);
    }

    private static long powSpecial(long base, int exp) {
        assert -2 &lt;= base &amp;&amp; base &lt;= 2 || base == Long.MIN_VALUE;
        final long sign = 1 - ((exp&amp;1) &lt;&lt; 1);

        switch ((int) base) {
            case -2: return exp&gt;=63 ? saturate(sign) : sign &lt;&lt; exp;
            case -1: return sign;
            case 0: return base&lt;0 ? saturate(sign) : 0;
            case 1: return base;
            case 2: return exp&gt;=63 ? Long.MAX_VALUE : 1L &lt;&lt; exp;
        }

        throw new RuntimeException("impossible");
    }

    private static long powUnsaturated(long base, int exp) {
        long result = 1;
        for (long x=base; exp&gt;0; exp&gt;&gt;=1) {
            if ((exp&amp;1) != 0) result *= x;
            x *= x;
        }
        return result;
    }

    public static long mul(long x, long y) {
        final long result = x * y;
        // See https://goo.gl/ZMEZEa
        final int nlz = Long.numberOfLeadingZeros(x) + Long.numberOfLeadingZeros(~x)
                + Long.numberOfLeadingZeros(y) + Long.numberOfLeadingZeros(~y);
        if (nlz &gt; 65) return result;
        if (nlz &lt; 64) return saturate(x^y);
        if (x==Long.MIN_VALUE &amp; y&lt;0) return Long.MAX_VALUE;
        if (y != 0 &amp;&amp; result / y != x) return saturate(x^y);
        return result;
    }

    public static long square(long x) {
        if (x &gt; +FLOOR_SQRT_MAX_LONG) return Long.MAX_VALUE;
        if (x &lt; -FLOOR_SQRT_MAX_LONG) return Long.MAX_VALUE;
        return x * x;
    }

    public static long cube(long x) {
        if (x &gt; +FLOOR_CBRT_MAX_LONG) return Long.MAX_VALUE;
        if (x &lt; -FLOOR_CBRT_MAX_LONG) return Long.MIN_VALUE;
        return x * x * x;
    }

    private static long saturate(long sign) {
        return saturate(sign &lt; 0);
    }

    private static long saturate(boolean negative) {
        return negative ? Long.MIN_VALUE : Long.MAX_VALUE;
    }

    // (long) Math.sqrt(Long.MAX_VALUE)
    private static final long FLOOR_SQRT_MAX_LONG = 3037000499L;
    // (long) Math.cbrt(Long.MAX_VALUE)
    private static final long FLOOR_CBRT_MAX_LONG = (1L &lt;&lt; 21) - 1;

    // For n&gt;=3, the n-th item is the n-th root of Long.MAX_VALUE.
    // The first three values are unused.
    private static final int[] FLOOR_ROOTS_MAX_LONG = {
        0, 0, 0, 2097151, 55108, 6208, 1448, 511,
        234, 127, 78, 52, 38, 28, 22, 18,
        15, 13, 11, 9, 8, 7, 7, 6,
        6, 5, 5, 5, 4, 4, 4, 4,
        3, 3, 3, 3, 3, 3, 3, 3,
        // The next value would be 2, so we stop here.
    };
}
It looks good to me, except for a couple of things:


private static long saturate(boolean negative) {
    return negative ? Long.MIN_VALUE : Long.MAX_VALUE;
}



Is there a particular reason you did negative instead of positive? It feels like an arbitrary choice to me. If it's not, add a brief comment explaining why. If it is, the convention (well, that I've seen, which means that it might well be the opposite) is to have true mean positive, not negative.


private static long powSpecial(long base, int exp) {



How is it special? Explain in the method name or a Javadoc comment (/** */). Here, it seems like it's for small numbers, so a better method name would be powSmallBases. It may only be used here, but it's rather convenient to be able to read your own code later, if you want to change it later.

Anyway, aside from that (and the things you mention in your coding style page thingamabobber) it looks good! Nicely done.