RFR: 8077587: BigInteger Roots [v15]

[fabioromano1]

On Thu, 10 Jul 2025 15:21:10 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> @rgiulietti Regarding the tests for _n_-th root, the tests for `sqrt()` could be extended in order to test also `nthRoot()`.
>
> @fabioromano1 IIUC, the bulk of the code in the PR is aimed at finding a good starting estimate.
> Algorithm 1.14 RootInt in [Brent & Zimmermann](https://maths-people.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf), p. 27-28, however, works for any initial estimate $u$ meeting $u \ge \lfloor m^{1/k}\rfloor$.
> 
> Now, assume $2^{l-1} \le m < 2^l$. We have $m^{1/k} < 2^{l/k} \le 2^{\lceil l/k\rceil}$
> Thus, the initial estimate could be simple as $u = 2^{\lceil l/k\rceil}$.
> 
> This has the following advantages:
> * It's super-easy to determine.
> * Computing the _first_ $t = (k - 1) s + \lfloor m/s^{k-1}\rfloor$ (L.4 of RootInt) is quite efficient and can be done separately using shifts and additions.
> 
> I don't know if this has some negative impact on performance in practice, but IMO the resulting code is easier to review, understand, and maintain.
> 
> Maybe worth giving it a try.
> WDYT?

@rgiulietti It should be noted that the convergence of Newton's method is quadratic, meaning the number of correct bits doubles with each iteration. This means that, to keep the number of iterations low, the larger the input, the greater the need for as many initial correct bits as possible.

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

PR Comment: https://git.openjdk.org/jdk/pull/24898#issuecomment-3058165927