RFR: 8077587: BigInteger Roots [v15]

[Raffaello Giulietti]

On Sat, 17 May 2025 11:25:58 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> The [Rampdown Phase One](https://openjdk.org/projects/jdk/25/) for JDK 25 is about 3 weeks from now.
>> 
>> I think it's a bit too late for API additions to be approved in due time. And even if we could rush this work for 25, it makes little sense to have this in 25 and the future one in 26. IMO, they should be released together. So this and the followup PR for `BigDecimal` will probably be integrated only in 26.
>> 
>> In other words, take your time ;-)
>
> @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?

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

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