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

[Raffaello Giulietti]

On Wed, 30 Apr 2025 15:59:05 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:
> 
>   Simplify long power computing

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

> 2620: 
> 2621:         // Factor the powers of two out quickly by shifting right, if needed.
> 2622:         if (powersOfTwo > 0) {

`shiftRight()` returns `this` when the shift distance is 0, so there's no compelling need to have two branches for `powersOfTwo`

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

> 2624:             remainingBits = base.bitLength();
> 2625:             if (remainingBits == 1) {  // Nothing left but +/- 1?
> 2626:                 if (signum < 0 && (exponent&1) == 1) {

This `boolean` expression occurs many times.
It could be factored out in a local var.

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

> 2654: 
> 2655:             // Multiply back the powers of two (quickly, by shifting left)
> 2656:             return powersOfTwo == 0

I don't think there's a compelling need to "optimize" for `powersOfTwo == 0`.

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

> 2660:                             : new BigInteger(result, newSign).shiftLeft(bitsToShift));
> 2661:         } else {
> 2662:             if ((((bitLength() - 1L) * exponent) >>> 5) + 1L > MAX_MAG_LENGTH) {

Suggestion:

            if ((bitLength() - 1L) * exponent >= 32L * MAX_MAG_LENGTH) {

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

> 2716:             x *= x;
> 2717:         }
> 2718:         return pow;

This uselessly computes a square in the last iteration.
See the [suggested variant](https://github.com/openjdk/jdk/pull/24690#discussion_r2068549452) for inspiration.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077472392
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077465904
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077482776
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077473938
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077478542