JDK 8 code review request for initial unsigned integer arithmetic library support

[Eamonn McManus]

It's great to see this! The API looks reasonable to me.

> For the first cut, I've favored keeping the code straightforward over
trickier but potentially faster algorithms.

The code looks clean and correct to me. But I think we could afford one or
two cheap improvements to Long without diving into the full-blown Hacker's
Delight algorithms:

In toUnsignedBigInteger(i) we could check whether i is nonnegative and use
plain BigInteger.valueOf(i) in that case. Also, although the difference is
sure to be unmeasurable, I think (int) (i >>> 32) would be better
than (int) ((i >> 32) & 0xffffffff).

In parseUnsignedLong, we can avoid using BigInteger by parsing all but the
last digit as a positive number and then adding in that digit:
    long first = parseLong(s.substring(0, len - 1), radix);
    int second = Character.digit(s.charAt(len - 1), radix);
    if (second < 0) {
        throw new NumberFormatException("Bad digit at end of " + s);
    }
    long result = first * radix + second;
    if (compareUnsigned(result, first) < 0) {
        throw new NumberFormatException(String.format("String value %s
exceeds " +
                                                        "range of unsigned
long.", s));
    }
By my measurements this speeds up the parsing of random decimal unsigned
longs by about 2.5 times. Changing the existing code to move the limit
constant to a field or to test for overflow using bi.bitLength() instead
still leaves it about twice as slow.

In divideUnsigned, after eliminating negative divisors we could check
whether the dividend is also nonnegative and use plain division in that
case.

In remainderUnsigned, we could check whether both arguments are nonnegative
and use plain % in that case, and we could also check whether the divisor
is unsigned-less than the dividend, and return it directly in that case.

Éamonn


On 13 January 2012 21:26, Joe Darcy <joe.darcy at oracle.com> wrote:

> Hello,
>
> Polishing up some work I've had *almost* done for a long time, please
> review an initial take on providing library support for unsigned integer
> arithmetic:
>
>    4504839 Java libraries should provide support for unsigned integer
> arithmetic
>    4215269 Some Integer.toHexString(int) results cannot be decoded back to
> an int
>    6322074 Converting integers to string as if unsigned
>
>    http://cr.openjdk.java.net/~**darcy/4504839.1/<http://cr.openjdk.java.net/~darcy/4504839.1/>
>
> For the first cut, I've favored keeping the code straightforward over
> trickier but potentially faster algorithms.  Tests need to be written for
> the unsigned divide and remainder methods, but otherwise the regression
> tests are fairly extensive.
>
> To avoid the overhead of having to deal with boxed objects, the unsigned
> functionality is implemented as static methods on Integer and Long, etc. as
> opposed to introducing new types like UnsignedInteger and UnsignedLong.
>
> (This work is not meant to preclude other integer arithmetic enhancements
> from going into JDK 8, such as add/subtract/multiply/divide methods that
> throw exceptions on overflow.)
>
> Thanks,
>
> -Joe
>
>
>