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

[Raffaello Giulietti]

On Sat, 27 Jul 2024 09:40:54 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:
> 
>   More accurate condition for MBI.safeRightShift()

Some comments on the benchmarks.

test/micro/org/openjdk/bench/java/math/BigIntegerSquareRoot.java line 57:

> 55:     public void setup() {
> 56:         Random r = new Random(1123);
> 57:         int numbits = r.nextInt(16384);

This value is not used.
In fact, the benchmarks only exercise integers up to about 2^66, which can hardly be defined as "huge".

test/micro/org/openjdk/bench/java/math/BigIntegerSquareRoot.java line 74:

> 72: 
> 73:         for (int i = 0; i < TESTSIZE; i++) {
> 74:             int value = Math.abs(r.nextInt());

There's a risk of an overflow here if the random `int` is `MIN_VALUE`, which would throw an exception later.

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

PR Review: https://git.openjdk.org/jdk/pull/19710#pullrequestreview-2203164205
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1693945489
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1693945509