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

[Raffaello Giulietti]

On Thu, 1 Aug 2024 10:16:59 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:
> 
>   Last small changes

Mmh, benchmarks show a slight slowdown with the iterative variant (except for the XS case). I tried several times, this one is the most favorable run:

Benchmark                        Mode  Cnt      Score     Error  Units
BigIntegerSquareRoot.testSqrtL   avgt   15   2862.103 ?  14.482  ns/op
BigIntegerSquareRoot.testSqrtM   avgt   15    767.569 ?  22.197  ns/op
BigIntegerSquareRoot.testSqrtS   avgt   15    249.484 ?  48.970  ns/op
BigIntegerSquareRoot.testSqrtXL  avgt   15  22324.068 ? 147.290  ns/op
BigIntegerSquareRoot.testSqrtXS  avgt   15      4.815 ?   0.108  ns/op

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

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