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

[Raffaello Giulietti]

On Sat, 27 Jul 2024 14:44:15 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 two additional commits since the last revision:
> 
>  - Correct test method name
>  - Updated sqrt speed test benchmark

On my M1 Pro/32 GiB

Current

Benchmark                                       Mode  Cnt        Score      Error  Units
BigIntegerSquareRoot.testBigSqrtAndRemainder    avgt   15       45.655 ?    0.273  ns/op
BigIntegerSquareRoot.testHugeSqrtAndRemainder   avgt   15  1200587.822 ? 7358.024  ns/op
BigIntegerSquareRoot.testLargeSqrtAndRemainder  avgt   15       27.052 ?    0.143  ns/op
BigIntegerSquareRoot.testSmallSqrtAndRemainder  avgt   15       33.098 ?    0.207  ns/op


New

Benchmark                                       Mode  Cnt      Score    Error  Units
BigIntegerSquareRoot.testBigSqrtAndRemainder    avgt   15     21.110 ?  0.151  ns/op
BigIntegerSquareRoot.testHugeSqrtAndRemainder   avgt   15  21525.493 ? 36.219  ns/op
BigIntegerSquareRoot.testLargeSqrtAndRemainder  avgt   15     14.897 ?  0.257  ns/op
BigIntegerSquareRoot.testSmallSqrtAndRemainder  avgt   15     15.539 ?  0.146  ns/op


Nice!

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

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