RFR: 4837946: Faster multiplication and exponentiation of large integers [v34]

[Chen Liang]

On Sat, 26 Apr 2025 16:44:26 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:
> 
>   Removed  method used by nth-root

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

> 2715:         int blockLen;
> 2716:         for (int nLen = Integer.SIZE - nZeros; nLen > 0; nLen -= blockLen) {
> 2717:             blockLen = maxExpLen < nLen ? maxExpLen : nLen;

`blockLen` can be defined in the loop like:

int blockLen = Math.min(maxExpLen, nLen);

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

> 2726:             if (exp > 0) {
> 2727:                 BigInteger xToExp = powerCache[exp];
> 2728:                 if (xToExp == null) {

Can we extract the cache computation logic into a new method for clarity? Huge methods hamper readability.

This use site will look like:

if (exp > 0) {
    BigInteger xToExp = powerCache[exp];
    if (xToExp == null) {
        xToExp = computePower(powerCache, x, exp, maxExp);
    }
}


`computePower` stores entries to `powerCache` whenever it computed something to allow  reuse.

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

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