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

[fabioromano1]

On Tue, 23 Jul 2024 14:42:36 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

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

@rgiulietti As I had already pointed out previously, the pseudocode in the paper assumes that the input is normalized, but the argument provided in the recursive invocation of the pseudocode could be not normalized, therefore actually also the algorithm in the paper requires that normalization must be performed at each invocation. The normalization performed in `sqrtRem()`, together with that in `sqrtRemZimmermann()`, guarantees that the assumpion L/4 <= N' in the paper's pseudocode is satisfied (in the paper of Bertot, Magaud, Zimmermann the assuption is incorrectly reported as L/4 < N', but in the original paper of Zimmermann is a_3 >= b/4 correctly).

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

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