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

[Raffaello Giulietti]

On Thu, 18 Jul 2024 17:22:50 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:
> 
>   Conditions' order reversed in MBI.ulongSqrt()

As I see it, there are some advantages in making the PR code as similar as possible to the code in the paper:
* It might result in simpler code (and maybe even faster code).
* It would make the Java code easier to compare to the C code in the paper. This would cause less head scratches to reviewers and contributors that might want to evolve the code.
* Since we know that (a variant) of that C code is in production since many years in GMP, and since that code has been formally verified, there's more confidence about its correctness.

Now, the C code has some obscure logic for the division by 2 S'. There's no stringent need to emulate that part, I think. Also, the logic for the 1 bit return value of the C function might be too cumbersome to emulate in the Java code.

Anyway, I think it would be beneficial to avoid the denormalization step in the recursive `sqrtRemZimmermann()` method. If possible, normalization and denormalization should only happen once in `sqrtRem()`.

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

PR Comment: https://git.openjdk.org/jdk/pull/19710#issuecomment-2247473366