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

[Raffaello Giulietti]

On Tue, 29 Apr 2025 20:33:29 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:
> 
>   Simplified the formula for detecting overflows

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

> 2735:         }
> 2736: 
> 2737:         return pow;

Is there a reason this cannot simply be the traditional "repeated square" method?
Why this complexity?

Suggestion:

        if (x == 1L)
            return 1L;

        if (x == 2L)
            return 1L << n;

        /*
         * The method assumption means that n <= 40 here.
         * Thus, the loop body executes at most 5 times.
         */ 
        long pow = 1;
        for (; n > 1; x *= x, n >>>= 1) {
            if ((n & 0b1) != 0) {
                pow *= x;
            }
        }
        return pow * x;

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

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