4
\$\begingroup\$

For project Euler, I need quite often to test things like is x*y*z < 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>=0);

        // Handle small bases and also Long.MIN_VALUE
        if (Math.abs(base) <= 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 >= FLOOR_ROOTS_MAX_LONG.length) return saturate(base < 0 && (exp&1) != 0);

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

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

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

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

        throw new RuntimeException("impossible");
    }

    private static long powUnsaturated(long base, int exp) {
        long result = 1;
        for (long x=base; exp>0; exp>>=1) {
            if ((exp&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 > 65) return result;
        if (nlz < 64) return saturate(x^y);
        if (x==Long.MIN_VALUE & y<0) return Long.MAX_VALUE;
        if (y != 0 && result / y != x) return saturate(x^y);
        return result;
    }

    public static long square(long x) {
        if (x > +FLOOR_SQRT_MAX_LONG) return Long.MAX_VALUE;
        if (x < -FLOOR_SQRT_MAX_LONG) return Long.MAX_VALUE;
        return x * x;
    }

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

    private static long saturate(long sign) {
        return saturate(sign < 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 << 21) - 1;

    // For n>=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.
    };
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Just to let you know, I read through this all and didn't find any problems with it. I didn't have enough to say to warrant an actual answer. \$\endgroup\$ – JS1 Jun 6 '15 at 8:54
  • \$\begingroup\$ @JS1 Thanks for the info. I've got a few ideas in the meantime and the multiplication is way faster now. The green bars are for the original Guava-inspired methods. I see there no green in the link. :D Use colors for the first column and move it to the right. \$\endgroup\$ – maaartinus Jun 6 '15 at 13:28
  • \$\begingroup\$ "Since BigInteger is usually too slow..." - If you have C++ experience, you might look at Crypto++. I began using it in college about 17 years ago when I needed a number theoretic library with big integers. C++ operator overloading makes the code somewhat readable, too. But you might be trading the devil you know for the devil you don't know.... \$\endgroup\$ – user53032 Jun 11 '15 at 23:33
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Concerning negative, it's actually the sign bit of the result. That's a very weak reason, but I'm unaware of any opposing reason. I can't remember having seen something like this (or the opposite). +++ powSpecial could be called powBasesSmallInAbsoluteValueAndLongMinValue to be exact. OTOH powSmallBases is imprecise, but otherwise a good name, so I'll go for it. \$\endgroup\$ – maaartinus Jun 11 '15 at 23:34
  • 1
    \$\begingroup\$ @maaartinus A weak reason is better than none. Again, I'd add a comment there -- literally just // Sign bit is 1 for negative, 0 for positive would do the trick. Also, powSmallBases may be inaccurate, but it's probably close enough. You could easily add a Javadoc comment to further explain. \$\endgroup\$ – Fund Monica's Lawsuit Jun 11 '15 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.