RFR: 8077587: BigInteger Roots [v45]

[fabioromano1]

On Fri, 25 Jul 2025 15:24:22 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1967:
>> 
>>> 1965:                     sToN1 = BigInteger.unsignedLongPow(sLong, n - 1);
>>> 1966:                     u = ((n - 1) * sLong + Long.divideUnsigned(x, sToN1)) / n;
>>> 1967:                 } while (u < sLong); // Terminate when non-decreasing.
>> 
>> I'm not sure this is 100% correct.
>> Since one "iteration" is done before even entering the loop, I think the loop condition should go to the beginning.
>> As it is now, there are always two evaluations of the Newton recurrence formula.
>
> No, the loop condition should not go to the beginning, because the 1st iteration is not related with the loop, but it serves to satisfy the precondition that guarantees the correctness after the termination of the loop. Indeed, the loop condition can't be evaluated after the first iteration, because `u` is not defined yet. If it were, doing the 1st iteration in the loop would make no difference, but the loop could stop with a wrong value of `s`.

> As it is now, there are always two evaluations of the Newton recurrence formula.

In other words, two evaluations of the Newton recurrence are always needed.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2231438424