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

[Raffaello Giulietti]

On Wed, 31 Jul 2024 18:52:12 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:
> 
>   Memory usage optimization

On Apple M1 Pro/32 GiB

before

Benchmark                        Mode  Cnt        Score      Error  Units
BigIntegerSquareRoot.testSqrtL   avgt   15   199747.794 ? 6173.446  ns/op
BigIntegerSquareRoot.testSqrtM   avgt   15    14902.574 ? 1291.014  ns/op
BigIntegerSquareRoot.testSqrtS   avgt   15     2093.805 ?   76.538  ns/op
BigIntegerSquareRoot.testSqrtXL  avgt   15  1188345.044 ? 1049.728  ns/op
BigIntegerSquareRoot.testSqrtXS  avgt   15       19.693 ?    0.350  ns/op


after

Benchmark                        Mode  Cnt      Score     Error  Units
BigIntegerSquareRoot.testSqrtL   avgt   15   2760.508 ?  56.561  ns/op
BigIntegerSquareRoot.testSqrtM   avgt   15    724.419 ?  30.709  ns/op
BigIntegerSquareRoot.testSqrtS   avgt   15    193.664 ?   0.689  ns/op
BigIntegerSquareRoot.testSqrtXL  avgt   15  21068.074 ? 358.149  ns/op
BigIntegerSquareRoot.testSqrtXS  avgt   15      4.871 ?   0.096  ns/op


Impressive!

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

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