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

[fabioromano1]

On Tue, 9 Jul 2024 17:17:48 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

> 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.

@rgiulietti The input is normalized in the method called `sqrtRemZimmermann`, and is normalized to a number of words which is a multiple of 4, and of course a multiple of 4 is even. For speed, the normalization is performed only "logically",
 which means that the contents of the input are not changed, but only its logical length, which is stored in the variable `len`.
The reason why the length is normalized to a mutiple of 4 is that, in this way, the input can be always split in blocks of words without twiddling with bits.

I am completely available for further clarifications regarding the algorithm code.

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

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