RFR: 8077587: BigInteger Roots [v45]

[fabioromano1]

On Fri, 25 Jul 2025 14:57:10 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Round up to do less iterations
>>   
>>   With the 1st iteration outside the loop, it is more convenient rounding up to ceiling.
>
> 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 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`.

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

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