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

[Raffaello Giulietti]

On Wed, 17 Jul 2024 15:33:39 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 comment

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

> 1971: 
> 1972:             /* For every long value s in [0, 2^32) such that x == s * s,
> 1973:              * it is true that s == Math.round(Math.sqrt(x >= 0 ? x : x + 0x1p64)),

To reinforce this claim, I suggest to add a test for all perfect squares.

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

> 1973:              * it is true that s == Math.round(Math.sqrt(x >= 0 ? x : x + 0x1p64)),
> 1974:              * and if x == 2^64 - 1, then Math.round(Math.sqrt(x >= 0 ? x : x + 0x1p64)) == 2^32.
> 1975:              * This means that the value returned by Math.round(Math.sqrt())

Suggestion:

             * Since both `Math.round()` and `Math.sqrt()` are (weakly) increasing,
             * this means that the value returned by `Math.round(Math.sqrt())`

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

> 2039: 
> 2040:             // Allocate sufficient space to hold the normalized final square root
> 2041:             MutableBigInteger sqrt = new MutableBigInteger(new int[(intLen + ((-intLen) & 3)) >> 1]);

Rather than expecting the reader to stop for some minutes to figure out what's happening with the arithmetic here, add a comment or prefer
Suggestion:

            MutableBigInteger sqrt = new MutableBigInteger(new int[2 * Math.ceilDiv(intLen, 4)]);

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

> 2075:         sqrt.shiftAdd(q, blockLen);
> 2076: 
> 2077:         MutableBigInteger chunk = u; // Corresponds to ub + a_0 in the paper

As observed in the past, there seems to be no point in having `chunk`, which is just an alias for `u`. You can use `u` directly.

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

> 2126: 
> 2127:     /**
> 2128:      * Returns a {@code MutableBigInteger} obtained taking {@code blockLen} ints from

Suggestion:

     * Returns a {@code MutableBigInteger} obtained by taking {@code blockLen} ints from

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

> 2133:      * @param limit the offset which is the end of valid words in the input value
> 2134:      * @param blockLen the length of the block in units of 32 bits
> 2135:      */

At first, I couldn't understand that `blockIndex` goes in the opposite direction as the array indices. Also, "starting" is very confusing, because no `int` at `blockIndex*blockLen` gets copied AFAIU.

Two improvements:
* Add a `@return` tag. Alternatively, use comments other than JavaDoc `/**`.
* Make it explicit that the direction of `blockIndex` is the opposite of the array indices, and reconsider the wording like "starting", etc.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1682861205
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1682861681
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1682862246
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1682862627
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1682862962
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1682863810