RFR: 8077587: BigInteger Roots [v23]

[Raffaello Giulietti]

On Wed, 23 Jul 2025 21:11:16 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> 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) := [ (n-1) t + m/t^{n-1}] / 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 [(n-1) t + m/t^{n-1}] / n \rfloor = \lfloor  \lfloor (n-1) t + m/t^{n-1}  \rfloor / 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.

Everything above is already present in BZ, except for your insight that $\lfloor f(s)\rfloor = \hat{f}(s)$, where $\hat{f}$ is the integer-valued recurrence function computed by the algorithm.
So yes, this is a proof that an initial positive integer underestimate leads to a (weak) integer overestimate after one iteration. From then on, BZ shows termination and correctness.

I think that a note in a comment like the following would be helpful:
"The integer-valued recurrence formula in the algorithm of Brent&Zimmermann simply discard the fraction part of the real-valued Newton recurrence on f discussed in the referenced work. As a consequence, an initial underestimate (not discussed in BZ) will immediately lead to a (weak) overestimate during the 1st iteration, thus meeting BZ requirements for termination and correctness."

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

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