RFR: 8077587: BigInteger Roots [v23]

[Raffaello Giulietti]

On Mon, 14 Jul 2025 15:40:18 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> 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.
>
> @rgiulietti The convergence of the recurrence is guaranteed if the initial estimate is larger than or equal to the exact value, AFAIK no guarantee is given when the estimate is smaller than the exact value.

This is my hunch as well.
So while the use of `nextUp()` and `ceil()` certainly help to achieve an overestimate, I'm less sure that this is sufficient when using `pow()`. If the latter has some error bigger than a few ulps, then we are in trouble.

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

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