On Wed, 23 Jul 2025 17:40:22 GMT, fabioromano1 <d...@openjdk.org> wrote:
>> 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)$ ).
I noticed the usage of exp() and log(), thanks for the change.
My concerns about using transcendental are rooted in [this
paper](https://members.loria.fr/PZimmermann/papers/accuracy.pdf).
The Javadoc claims an error of 1 ulp for pow(), but it turns out to be plainly
wrong: the worst _known_ error is 636 ulps! (In that paper, see the column for
OpenLibm, a derivative work of fdlibm.)
On a more positive side, that paper also shows the worst _known_ error for
exp() and log() to be around 0.95 ulps. But again, it could be much worse, who
knows?
The Brent & Zimmermann paper assumes an initial estimate $u \ge \lfloor
x^{1/n}\rfloor$, probably for a (unstated) reason.
The proof of the algorithm makes use of Newton's formula $x_{i+1} = f(x_i)$,
where $f$ is the real-valued counterpart of the integer recurrence formula in
the algorithm.
It is straightforward to see that $x_{i+1} > x^{1/n}$ when $0 < x_i < x^{1/n}$.
But it's less clear to me that the same applies to the _integer_ recurrence
formula of the algorithm.
Given all of the above, we must ensure that the initial estimate meets the
requirements of the BZ paper, or we need a proof that an underestimate in the
1st iteration is harmless because it will become an overestimate in the 2nd,
i.e., that the reasoning which holds for the real-valued $f$ also holds with
the integer-valued analogous formula.
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2226499267
