RFR: 8355719: Reduce memory consumption of BigInteger.pow() [v51]

[fabioromano1]

On Wed, 7 May 2025 17:43:30 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>>> Ah right, but you probably want
>> 
>> No, the sufficient condition to get the overflow is `(bitLength() - 1L) * exponent + 1L > Integer.MAX_VALUE`, which is equivalent to that one I wrote above.
>
> At some point you proposed
> 
> (bitLength() - 1L) * exponent >= (long) MAX_MAG_LENGTH << 5
> 
> Given the value of `MAX_MAG_LENGTH`, which is 2^26, this is equivalent to
> 
> (bitLength() - 1L) * exponent >= 1L << 31
> 
> that is, to
> 
> (bitLength() - 1L) * exponent > Integer.MAX_VALUE
> 
> 
> What am I missing?

The condition `A := (bitLength() - 1L) * exponent + 1L > Integer.MAX_VALUE` is more accurate, as it compares the bit length of the result, in fact `B := (bitLength() - 1L) * exponent >= (long) MAX_MAG_LENGTH << 5` implies `A`, but `A` does not imply `B`. The `BigInteger`s can have a mag length up to `MAX_MAG_LENGTH`, but `MAX_MAG_LENGTH * Integer.SIZE > Integer.MAX_VALUE`.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2078174586