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

[fabioromano1]

On Wed, 24 Jul 2024 10:07:48 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

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

Initially, when I implemented the algorithm, I almost completely ignored the C code in the paper, because it seemed very obscure to me, and I relied solely on the logic of the pseudocode, even at the cost of writing a less efficient program.

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

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