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

[Raffaello Giulietti]

On Wed, 7 May 2025 17:51:05 GMT, fabioromano1 <duke at openjdk.org> wrote:

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

OK.

But then your original expression

(((bitLength() - 1L) * exponent) >>> 5) + 1L > MAX_MAG_LENGTH

was a bit too restrictive as well, right?

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

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