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

[Chen Liang]

On Sat, 26 Apr 2025 19:11:01 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:
> 
>   Put power's computation in a stand-alone method

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

> 2640:         // Use slightly different algorithms for small and large operands.
> 2641:         // See if the result will safely fit into a long. (Largest 2^63-1)
> 2642:         if (base.mag.length == 1 && scaleFactor <= 62) {

It seems your new `unsignedIntPow` already covers `base.mag.length == 1` case - your `unsignedLongPow` and `unsignedIntPow` are otherwise identical. Can we just remove this long shortcut and `unsignedLongPow` and use the newly established `unsignedIntPow`? That can also remove lots of redundant code and significantly reduce maintenance cost. (Unless BigInteger.multiply(long) is much cheaper than BigInteger.multiply(BigInteger))

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

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