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

[Raffaello Giulietti]

On Tue, 2 Jul 2024 01:44:43 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:
> 
>   Ensure normalized value in MutableBigInteger initialization with ints

Let's agree that the reference for this PR is the [algorithm](https://inria.hal.science/inria-00072113/document) described by Bertot, Magaud and Zimmermann.

>From a first reading, the algorithm implemented here appears different in many aspects from the one in the paper, making a direct comparison between the twos rather hard.
For example, the paper normalizes the input to an even number of words ("limbs"). AFAIU, this doesn't seem to happen here. There might be good reasons to depart from what is described in the paper, but there's no discussion.

To ease the reviewing process, and for the benefit of future maintainers, every departure from the paper should be discussed and mathematically justified to some extent in comments.

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

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