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()

AFAIU, in the Bertot, Magaud, Zimmermann paper there is just one "denormalization" step in the wrapper, before returning the final result to the client.

Here, there seems to be a denormalization before returning from each recursive invocation with a length > 2 in `sqrtRemZimmermann()`, and one final denormalization in `sqrtRem()`.

If my understanding is correct, I wonder if the scheme on the paper has been considered as an alternative, and if so, what the advantages of this PR code are.

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

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