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

The last small changes...

src/java.base/share/classes/java/math/MutableBigInteger.java line 1960:

> 1958:             sqrt.value[0] = (int) s;
> 1959: 
> 1960:             // The first invocation is never a base case, so the remainder is needed

This comment is confusing and contradicts the comment right at the beginning of the method.
I think it can be removed.

src/java.base/share/classes/java/math/MutableBigInteger.java line 1991:

> 1989:         if (needRemainder) {
> 1990:             rem = u;
> 1991:             if (rem.subtract(qSqr) == -1) {

For robustness, prefer
Suggestion:

            if (rem.subtract(qSqr) < 0) {

src/java.base/share/classes/java/math/MutableBigInteger.java line 1994:

> 1992:                 MutableBigInteger twiceSqrt = new MutableBigInteger(sqrt);
> 1993:                 twiceSqrt.leftShift(1);
> 1994: 

Maybe add a comment that, because of the way `MBI.subtract` works`, the logic here is "reversed" w.r.t. the one in the paper.

src/java.base/share/classes/java/math/MutableBigInteger.java line 2001:

> 1999:         } else {
> 2000:             rem = null;
> 2001:             if (u.compare(qSqr) == -1)

Since you don't depend on the exact value returned by `compare` but only on its signum, it's more robust to write this as
Suggestion:

            if (u.compare(qSqr) < 0)

test/jdk/java/math/BigInteger/BigIntegerTest.java line 296:

> 294:     }
> 295: 
> 296:     private static void perfectSquaresLong() {

On L.2 please change the last copyright year from 2023 to 2024.

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

> 1: /*
> 2:  * Copyright (c) 2014, 2024, Oracle and/or its affiliates. All rights reserved.

Suggestion:

 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.

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

PR Review: https://git.openjdk.org/jdk/pull/19710#pullrequestreview-2212128217
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1699792998
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1699786653
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1699778380
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1699787332
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1699771929
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1699764168