RFR: 8077587: BigInteger Roots [v77]

[Raffaello Giulietti]

On Fri, 29 Aug 2025 07:18:03 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> This PR implements nth root computation for BigIntegers using Newton method.
>
> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Grammar correction

Small improvements

src/java.base/share/classes/java/math/MutableBigInteger.java line 1979:

> 1977:             s = new MutableBigInteger(sLong);
> 1978:         } else {
> 1979:             final int rootLen = (bitLength - 1) / n + 1;

Suggestion:

            final int rootLen = (bitLength - 1) / n + 1;  // ⌈bitLength / n⌉

src/java.base/share/classes/java/math/MutableBigInteger.java line 1986:

> 1984:                 // The initial estimate will be 2^rootLen == 2 << (rootLen - 1)
> 1985:                 rootSh = rootLen - 1;
> 1986:             } else {

What about swapping the "then" and "else" branches?
IMO, the current "else" contains more context/comments to understand the current "then", so should come before.

src/java.base/share/classes/java/math/MutableBigInteger.java line 1993:

> 1991:                  * to get an upper bound of the root of x, it suffices to find an integer sh
> 1992:                  * and a real s such that s >= nthRoot(x/2^sh, n) and sh % n == 0.
> 1993:                  * The uppper bound will be s * 2^(sh/n), indeed:

Suggestion:

                 * The upper bound will be s * 2^(sh/n), indeed:

src/java.base/share/classes/java/math/MutableBigInteger.java line 2000:

> 1998:                  * The value of the shift sh is chosen in order to have the smallest number of
> 1999:                  * trailing zeros in the double value of s after the significand (minimizing
> 2000:                  * non-significant bits), avoiding to lose bits in the significand.

Suggestion:

                 * non-significant bits), to avoid losing bits in the significand.

src/java.base/share/classes/java/math/MutableBigInteger.java line 2003:

> 2001:                  */
> 2002:                 // Determine a right shift that is a multiple of n into finite double range.
> 2003:                 int sh = bitLength - Double.PRECISION;

Suggestion:

                // sh < bitLength, so sh / n == rootSh < rootLen
                rootSh = (bitLength - Double.PRECISION) / n;
                int sh = rootSh * n;

and the other related changes below.

src/java.base/share/classes/java/math/MutableBigInteger.java line 2018:

> 2016:                  * since bl-(sh-ex) is its bit length.
> 2017:                  */
> 2018:                 sh -= sh % n; // Adjust shift to a multiple of n

Suggestion:

src/java.base/share/classes/java/math/MutableBigInteger.java line 2026:

> 2024:                 rad = Math.nextUp(rad);
> 2025:                 approx = nthRootApprox(rad, n);
> 2026:                 rootSh = sh / n; // sh < bitLength, so sh / n == rootSh < rootLen

Suggestion:

src/java.base/share/classes/java/math/MutableBigInteger.java line 2033:

> 2031:                 s = new MutableBigInteger((int) approx + 1);
> 2032:             } else {
> 2033:                 // Allocate sufficient space to store the final root

Suggestion:

                // Allocate ⌈intLen / n⌉ ints to store the final root

src/java.base/share/classes/java/math/MutableBigInteger.java line 2067:

> 2065:                  * initial estimate.
> 2066:                  */
> 2067:                 // Refine the estimate, avoiding to compute non-significant bits

Suggestion:

                // Refine the estimate to avoid computing non-significant bits

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

PR Review: https://git.openjdk.org/jdk/pull/24898#pullrequestreview-3168969219
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310332924
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310334647
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310334845
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310335236
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310336330
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310336716
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310336875
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310337231
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2310337537