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

[Raffaello Giulietti]

On Wed, 7 May 2025 18:32:50 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> This PR optimizes `BigInteger.pow(int)` method. The primary enhancement in `pow()` is not concerned most on execution time, but rather in memory optimization, because the PR implementation does the "shift of the exponent" squaring the result rather than the base, so the base is not squared like in the current implementation, and this permits to save about half of the memory.
>
> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Suggested changes

Last nits.

I'll approve the PR in the next couple of days for last minute small changes from you.

src/java.base/share/classes/java/math/BigInteger.java line 2656:

> 2654:             // Perform exponentiation using repeated squaring trick
> 2655:             // The loop relies on this invariant:
> 2656:             // base^exponent == answer^(2^expLen) * base^(exponent & (2^expLen - 1))

The invariant is correct, but it should minimally involve all running variables updated in the loop, including `workingExp`. Otherwise, reasoning about the invariant becomes harder.

Further, I suggest to replace the subexpression `exponent & (2^expLen - 1)` with the more mathematical `exponent % (2^expLen)`.

test/micro/org/openjdk/bench/java/math/BigIntegerPow.java line 62:

> 60:      * Each array entry is atmost 64 bits
> 61:      * in size
> 62:      */

This can be re-flowed more compactly like so (and similarly for the other fields)
Suggestion:

    private int xsExp = (1 << 20) - 1;
    /* Each array entry is at most 64 bits in size */
    private BigInteger[] xsArray = new BigInteger[TESTSIZE];

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

PR Review: https://git.openjdk.org/jdk/pull/24690#pullrequestreview-2824381118
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2079247545
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2079251316