On Wed, 30 Apr 2025 15:59:05 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:
>
> Simplify long power computing
src/java.base/share/classes/java/math/BigInteger.java line 2622:
> 2620:
> 2621: // Factor the powers of two out quickly by shifting right, if
> needed.
> 2622: if (powersOfTwo > 0) {
`shiftRight()` returns `this` when the shift distance is 0, so there's no
compelling need to have two branches for `powersOfTwo`
src/java.base/share/classes/java/math/BigInteger.java line 2626:
> 2624: remainingBits = base.bitLength();
> 2625: if (remainingBits == 1) { // Nothing left but +/- 1?
> 2626: if (signum < 0 && (exponent&1) == 1) {
This `boolean` expression occurs many times.
It could be factored out in a local var.
src/java.base/share/classes/java/math/BigInteger.java line 2656:
> 2654:
> 2655: // Multiply back the powers of two (quickly, by shifting
> left)
> 2656: return powersOfTwo == 0
I don't think there's a compelling need to "optimize" for `powersOfTwo == 0`.
src/java.base/share/classes/java/math/BigInteger.java line 2662:
> 2660: : new BigInteger(result,
> newSign).shiftLeft(bitsToShift));
> 2661: } else {
> 2662: if ((((bitLength() - 1L) * exponent) >>> 5) + 1L >
> MAX_MAG_LENGTH) {
Suggestion:
if ((bitLength() - 1L) * exponent >= 32L * MAX_MAG_LENGTH) {
src/java.base/share/classes/java/math/BigInteger.java line 2718:
> 2716: x *= x;
> 2717: }
> 2718: return pow;
This uselessly computes a square in the last iteration.
See the [suggested
variant](https://github.com/openjdk/jdk/pull/24690#discussion_r2068549452) for
inspiration.
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077472392
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077465904
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077482776
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077473938
PR Review Comment: https://git.openjdk.org/jdk/pull/24690#discussion_r2077478542
