RFC 6910473: BigInteger negative bit length, value range, and future prospects

[Joseph Darcy]

Hello,

A quick note on this issue, before the recent work to use better 
algorithms for BigInteger arithmetic operation, working with huge 
numbers was impractical and thus BigInteger.bitLength misbehavior was 
mostly an academic concern. With the better algorithms, exposure to 
these large values is likely to increase so BigInteger.bitLength should 
do something reasonable.

There are at least two implementation limits of note in the current code:

* Total bit length given a single backing array
* Max size of serializable BigInteger given old byte-array based format.

My preference for addressing this issue includes adding an 
implementation note along the lines of "in JDK 8, BigInteger operates on 
values in the range ...." without requiring that range to be part of the 
specification.

Cheers,

-Joe

On 6/25/2013 6:18 PM, Brian Burkhalter wrote:
> This request for comment regards this issue
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6910473
> BigInteger.bigLength() may return negative value for large numbers
>
> but more importantly Dmitry's thread
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/018345.html
> What is the range of BigInteger values?
>
> The issue may be fixed superficially simply by throwing an ArithmeticException if the bit length as an int would be negative. A better fix suggested both in the issue description and in the aforementioned thread (option 1 of 3), is to define BigInteger to support a limited range and to clamp to that range in the constructor, throwing an ArithmeticException if the supplied parameter(s) would cause the BigInteger to overflow. This check would be relatively inexpensive. The suggested constraint range is
> [ -pow(2, pow(2,31) - 1), pow(2, pow(2,31) - 1) )
> This constraint would guarantee that all BigInteger instances are capable of accurately returning their properties such as bit length, bit count, etc.
>
> This naturally would require a minor specification change to BigInteger. The question is whether this change would limit any future developments of this and related classes. For example, one could envision BigInteger supporting bit lengths representable by a long instead of an int. In this case the second option would be preferable.
>
> It has been suggested that an alternative to extending the ranges supported by BigInteger would be to define a different class altogether to handle the larger ranges, keeping BigInteger as a well-specified API for the ranges it supports. Other related classes for arbitrary precision binary floating point and rational numbers might also be considered.
>
> In summary the specific questions being posed here are:
>
> 1) what is the general opinion on clamping the range of BigInteger and the various options suggested at the end of
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/018345.html ?
>
> 2) what are the forward looking thoughts on handling integers outside the current BigInteger range?
>
>  From a practical point of view, any changes need to be considered with respect to what may be done in the short term (JDK 8) versus the long (JDK 9), so to speak.
>
> Thanks,
>
> Brian