On Thu, 18 Jul 2024 17:22:50 GMT, fabioromano1 <d...@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() 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()`. ------------- PR Comment: https://git.openjdk.org/jdk/pull/19710#issuecomment-2247473366
