Last week, I enjoyed attending the 2010 JVM Language Summit. Some of the requests from the "what the JVM needs" session could be addressed by a few additional numerical libraries in the platform.

The default integer arithmetic in many languages conceptually doesn't overflow, analogous to operating on Java's java.math.BigInteger objects rather than 32-bit int or 64-bit long values. However, small integers that enjoy hardware support on commodity CPUs are much more commonly operated on than big numbers which require multi-word support. Ideally, conceptually unbounded integers would still run very fast when they were small enough without consuming either excess CPU cycles or excess memory. In the limit, fixnums would result, where the transitions between small ↔ big integers were managed and optimized by the JVM. Until that happy day, internally BigDecimal manages long ↔ BigInteger transitions and potential future library additions could ease independently coding up similar logic.

Semantically a BigDecimal is a BigInteger significand/mantissa along with an int scale (negated exponent). If the scale/exponent is zero, then exact integer results can be computed. The BigDecimal implementation in the JDK internally often uses a long where possible to hold the significand value, failing over to allocating and operating on a BigInteger value when needed. The compact long representation is seamlessly supported in arithmetic and other operations. BigDecimal is not an ideal type for providing pure integer arithmetic since BigDecimal has many operations unneeded and inappropriate for that use and because each BigDecimal object has various fields other than the ones holding the integer value; however, the class comes with the JDK and may perform adequately out of the box.

The algorithms used for the long overflow checking in BigDecimal are adapted from the indispensable bit-twiddling tome Hacker's Delight. A few conference attendees expressed interest in an API around integer overflow detection. Represented as a Java API, the functionality might look like:

/** * Returns the sum of the arguments, throwing an ArithmeticException * if the exact sum is out of {@code int} range. * @return the sum of the arguments, throwing an ArithmeticException * if the exact sum is out of {@code int} range. * @throws ArithmeticException if the exact sum is out of {@code int} range */ public static int addExact(int a, int b) throws ArithmeticException The source code of such a method could use the Hacker's Delight techniques while a JVM could intrinsify the functionality to a processor-optimized idiom. There are some design choices even in this simple method. For example, instead of ArithmeticException, a new subclass of that exception called, say, IntegerOverflow, could be thrown instead. Such a subclass could offer the ability to store the original operands to facilitate continuing the computation in a wider type. (An unfriendly API design for the purposes at hand would be for addExact to have int parameters but return a java.lang.Integer, with null being used to indicate overflow occurred!)

While I don't recall it being explicitly mentioned at the conference, a piece of similar functionality is accessing the high-order 64 bits of a full 64 × 64 → 128 bit multiply (5100935).

Adding these low-level library operations to the platform would be a fun project!



Read More about [JVM Language Summit: Numbers big and fixed...