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

[Joe Darcy]

Hi Eamonn,

On 01/15/2012 09:53 AM, Eamonn McManus wrote:
> It's great to see this! 

I agree :-)

I've posted a revised webrev at

     http://cr.openjdk.java.net/~darcy/4504839.2

More detailed responses inline.

> 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).

Good points; changed.

>
> 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.

Changed.

Also from some off-list comments from Mike, I've modified the first 
sentence of the parseUnsignedLong methods to explicitly mention the 
"long" type; this is consistent with the phrasing of the signed 
parseLong methods in java.lang.Long.

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

Changed.

>
> 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.

Changed.

I've also added test cases for the unsigned divide and remainder methods.

Thanks again,

-Joe

>
> Éamonn
>
>
> On 13 January 2012 21:26, Joe Darcy <joe.darcy at oracle.com 
> <mailto: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/%7Edarcy/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
>
>
>