On Wed, 7 May 2025 18:32:50 GMT, fabioromano1 <[email protected]> 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:
>
> Suggested changes
Last nits.
I'll approve the PR in the next couple of days for last minute small changes
from you.
src/java.base/share/classes/java/math/BigInteger.java line 2656:
> 2654: // Perform exponentiation using repeated squaring trick
> 2655: // The loop relies on this invariant:
> 2656: // base^exponent == answer^(2^expLen) * base^(exponent &
> (2^expLen - 1))
The invariant is correct, but it should minimally involve all running variables
updated in the loop, including `workingExp`. Otherwise, reasoning about the
invariant becomes harder.
Further, I suggest to replace the subexpression `exponent & (2^expLen - 1)`
with the more mathematical `exponent % (2^expLen)`.
test/micro/org/openjdk/bench/java/math/BigIntegerPow.java line 62:
> 60: * Each array entry is atmost 64 bits
> 61: * in size
> 62: */
This can be re-flowed more compactly like so (and similarly for the other
fields)
Suggestion:
private int xsExp = (1 << 20) - 1;
/* Each array entry is at most 64 bits in size */
private BigInteger[] xsArray = new BigInteger[TESTSIZE];
-------------
PR Review: https://git.openjdk.org/jdk/pull/24690#pullrequestreview-2824381118
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2079247545
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2079251316
