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

[Eamonn McManus]

Hi Joe,

That looks great to me (emcmanus). One thing I noticed is that the
behaviour is not explicitly specified when parseUnsignedLong is given a
null String reference. But I see that is also true of the existing
parseLong and valueOf(String) and decode(String), so perhaps there should
be a separate bug to update the spec there. The phrase "If the string
cannot be parsed as a long" does not cover this case as obviously as it
might.

Cheers,
Éamonn


On 17 January 2012 18:54, Joe Darcy <joe.darcy at oracle.com> wrote:

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