On Wed, 23 Jul 2025 19:49:51 GMT, Raffaello Giulietti <rgiulie...@openjdk.org>
wrote:
>> @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.
@rgiulietti
> The Brent & Zimmermann paper assumes an initial estimate u ≥ ⌊ x 1 / n ⌋ ,
> probably for a (unstated) reason.
The reason is the condition to stop the loop, since it terminates when the
estimate does not decrease anymore.
>
> 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.
In Brent & Zimmermann proof, we have the following definition: $f(t) := \lfloor
(n-1) t + m/t^{n-1} \rfloor / n$, with $t \in (0; +\infty)$. Since $f(t)' < 0$
if $t < \sqrt[n]{m}$ and $f(t)' > 0$ if $t > \sqrt[n]{m}$, then $\sqrt[n]{m}$
is a point of minimum, so $f(t) \ge f(\sqrt[n]{m}) = \sqrt[n]{m}$, hence
$\lfloor f(t) \rfloor \ge \lfloor \sqrt[n]{m} \rfloor$ for any $t$ in the
domain. This proves that, when $\lfloor f(t) \rfloor \le \lfloor \sqrt[n]{m}
\rfloor$ becomes true (it does because the sequence of estimates is strictly
decreasing), we get $\lfloor f(t) \rfloor = \lfloor \sqrt[n]{m} \rfloor$ and
the loop stops at the next iteration.
> 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.
It should be clear if we note that the integer-valued analogous formula simply
discard the fraction part of the real-valued counterpart:
$\lfloor f(t) \rfloor = \lfloor \lfloor (n-1) t + m/t^{n-1} \rfloor / n
\rfloor$ = $\lfloor ((n-1) t + m/t^{n-1}) / n \rfloor$
So, if $x_i < \lfloor \sqrt[n]{m} \rfloor$, then $((n-1) x_i + m/x_i^{n-1}) / n
> \sqrt[n]{m}$, hence $\lfloor f(x_i) \rfloor \ge \lfloor \sqrt[n]{m} \rfloor$.
>From what has just been shown, it follows that it is sufficient to perform an
>initial iteration before starting the loop to get an overestimate.
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/24898#discussion_r2226698680
