RFR: 8077587: BigInteger Roots [v23]

[fabioromano1]

On Wed, 23 Jul 2025 17:05:07 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> @rgiulietti Now that I checked the recurrence better, it seems to me that it should give an overestimate if `rLong` is an underestimate, without modify it.
>
> Can you please provide a succinct "proof" in form of a comment? Needs to be convincing, although not necessarily rigorous.

@rgiulietti I've changed the formula that computes the initial estimate, now it does not use `Math.pow()` anymore, but `Math.exp()` and `Math.log()` instead, which are guaranteed to have always an error less than 1 ulp  by the fdlibm.

Anyway, the proof that the Newton's recurrence should output an overestimate if the input is an underestimate should follow by two facts:
- $f(x) = x^n - C$ with domain $x \in [0, +\infty)$ is an increasing function and its derivative is increasing;
- Newton's recurrence computes the next approximation $x_{i+1}$ by finding the zero of the line with gradient $f'(x_i)$ that passes through the point $(x_i, f(x_i))$.

So, Newton's method approximates the curve of $f(x)$ with the tangent in the point $(x_i, f(x_i))$. Since the curve is increasing and its derivative is increasing, if $x_i$ is less than the zero of $f(x)$, then the zero of the line must be greater than the zero of $f(x)$ (because the line increases more slowly than the curve of $f(x)$ ).

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

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