RFR: 8077587: BigInteger Roots [v23]

[Raffaello Giulietti]

On Sat, 12 Jul 2025 09:18:27 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:
> 
>   Removed useless instruction

I'm looking forward for better documentation for the initial estimate code and for the tests.

src/java.base/share/classes/java/math/BigInteger.java line 2750:

> 2748:      * {@code n}th root of the corresponding mathematical integer {@code x} has the
> 2749:      * same sign of {@code x}, and its magnitude is the largest integer {@code r}
> 2750:      * such that {@code r**n <= abs(x)}. It is equal to the value of

Please use HTML `<sup>`, `≤`, vertical bars, etc., when writing math in Javadoc.
Likewise for `⌊`,`⌋`, and whenever there are better typographic means to express math in Javadoc.
It's more tedious to write, but reads much better.

src/java.base/share/classes/java/math/BigInteger.java line 2803:

> 2801:     /**
> 2802:      * Assume {@code n != 1 && n != 2}
> 2803:      */

There's no need for Javadoc here.
Alternatively, it should document parameters, return value, etc., as usual.

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

> 165:      * Assume val is in the finite double range.
> 166:      */
> 167:     static MutableBigInteger valueOf(double val, int pow) {

Suggestion:

    private static MutableBigInteger valueOf(double val, int pow) {

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

> 1934:      * where {@code nthRoot(., n)} denotes the mathematical {@code n}th root.
> 1935:      * The contents of {@code this} are <em>not</em> changed. The value of {@code this}
> 1936:      * is assumed to be non-negative and the root degree {@code n >= 3}.

I don't think `this` can be negative, can it?

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

> 1938:      * @implNote The implementation is based on the material in Richard P. Brent
> 1939:      * and Paul Zimmermann, <a href="https://maths-people.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf">
> 1940:      * Modern Computer Arithmetic</a>, 27-28.

Suggestion:

     * Modern Computer Arithmetic</a>, p. 27-28.

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

> 1941:      *
> 1942:      * @return the integer {@code n}th root of {@code this} and the remainder
> 1943:      */

`@param` is missing.

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

> 1962:             final double rad = Math.nextUp(x >= 0 ? x : x + 0x1p64);
> 1963:             final double approx = n == 3 ? Math.cbrt(rad) : Math.pow(rad, Math.nextUp(1.0 / n));
> 1964:             long rLong = (long) Math.ceil(Math.nextUp(approx));

Does `rLong` need to be an overestimate of the true value, or does the algorithm also works for underestimates?
I'm asking because I'm not sure that `Math.pow()` has strong guarantees about its error bounds, whatever the documentation states.

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

> 1986:             // Try to shift as many bits as possible
> 1987:             // without losing precision in double's representation
> 1988:             if (bitLength > Double.PRECISION) {

This condition is always `true`, as `bitLength > Long.SIZE` holds here.

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

> 2007:             } else {
> 2008:                 shift = 0L;
> 2009:                 rad = this.toBigInteger().doubleValue();

By the above, this becomes useless.

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

PR Review: https://git.openjdk.org/jdk/pull/24898#pullrequestreview-3016614559
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205097131
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205098001
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205098431
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205098874
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205099587
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205099747
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205100318
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205100683
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2205100880