On Wed, 23 Jul 2025 17:05:07 GMT, Raffaello Giulietti <rgiulie...@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
