RFR: 8334755: Asymptotically faster implementation of square root algorithm [v28]

[Raffaello Giulietti]

On Mon, 15 Jul 2024 19:58:23 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> I have implemented the Zimmermann's square root algorithm, available in works [here](https://inria.hal.science/inria-00072854/en/) and [here](https://www.researchgate.net/publication/220532560_A_proof_of_GMP_square_root).
>> 
>> The algorithm is proved to be asymptotically faster than the Newton's Method, even for small numbers. To get an idea of how much the Newton's Method is slow,  consult my article [here](https://arxiv.org/abs/2406.07751), in which I compare Newton's Method with a version of classical square root algorithm that I implemented. After implementing Zimmermann's algorithm, it turns out that it is faster than my algorithm even for small numbers.
>
> fabioromano1 has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Optimized shift-and-add operations

src/java.base/share/classes/java/math/MutableBigInteger.java line 1978:

> 1976:              * is either correct, or rounded up by one if the value is too high
> 1977:              * and too close to the next perfect square.
> 1978:              */

Contrary to my previous believe and own experiments, I now think this code is incorrect.

Let `long t = 3037000503L` and `long x = t * t`. The code computes `long s == 3037000502L`, an underestimate of the correct square root `t` by 1. Underestimates are neither detected nor corrected.
Of course, the corresponding remainder `long r = x - s * s`, namely `r = 6074001005L`, is just barely too large as it does _not_ meet `r <= 2 * s`.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1681033100