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

[fabioromano1]

On Sat, 26 Apr 2025 17:22:09 GMT, Chen Liang <liach at openjdk.org> wrote:

>> src/java.base/share/classes/java/math/BigInteger.java line 2721:
>> 
>>> 2719:             if (!pow.equals(ONE)) {
>>> 2720:                 for (int i = 0; i < blockLen; i++)
>>> 2721:                     pow = pow.multiply(pow);
>> 
>> Majority of the time we have `blockLen == maxExpLen`. We should cache that pow-to-maxExpLen result too, if we have `maxExpLen >= nLen` initially. Maybe also calculate power-to-`nLen % maxExpLen` as that will be used in the final round of the loop.
>
> No, pow is always being modified, ignore this, my bad.

> Majority of the time we have `blockLen == maxExpLen`. We should cache that pow-to-maxExpLen result too, if we have `maxExpLen >= nLen` initially. Maybe also calculate power-to-`nLen % maxExpLen` as that will be used in the final round of the loop.

I don't get the point, since `pow` changes its value at every iteration and here the property of the "power of a power" is used, i.e. `pow^(2^n) == (((pow^2)^2)...)^2` `n` times to shift the exponent of the power, so I don't see how caching pow-to-maxExpLen would be useful.

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

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