RFR: 8077587: BigInteger Roots [v38]

[Raffaello Giulietti]

On Wed, 23 Jul 2025 16:11:20 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:
> 
>   More accurate lower bound for doubles values tests

Please merge branch `master` into yours every now and then.

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

> 1954:                     rToN1 = BigInteger.unsignedLongPow(rLong, n - 1);
> 1955:                     r1 = ((n - 1) * rLong + Long.divideUnsigned(x, rToN1)) / n;
> 1956:                 } while (r1 < rLong); // Terminate when non-decreasing.

Here (and below as well) it would be useful to have the same variable names as in the paper, where possible.
No need to rename `x` to m and `n` to k, though, they can remain.

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

> 1998:                     int shiftLack = n - shiftExcess;
> 1999:                     shift += shiftLack; // shift is long, no overflow
> 2000:                     rad /= Double.parseDouble("0x1p" + shiftLack);

Suggestion:

                    rad /= Math.scalb(1.0, shiftLack);

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

> 2024:                     int correctBits = ((Double.PRECISION - 1) - radExp - 1) / n + 1;
> 2025:                     rootShift -= correctBits;
> 2026:                     approx *= Double.parseDouble("0x1p" + correctBits);

Suggestion:

                    approx *= Math.scalb(1.0, correctBits);

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

PR Comment: https://git.openjdk.org/jdk/pull/24898#issuecomment-3109471808
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2226198312
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2226198452
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2226198568