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

Raffaello Giulietti rgiulietti at openjdk.org
Fri Jul 12 13:13:10 UTC 2024 

On Tue, 9 Jul 2024 20:06:40 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:
> 
>   Added comment on normalization in MutableBigInteger.sqrtRemZimmermann()

@fabioromano1 This is a first reading, comparing with the well documented algorithm in the Bertot, Margaud, Zimmermann paper.

src/java.base/share/classes/java/math/BigInteger.java line 2724:

> 2722:         if (this.signum < 0) {
> 2723:             throw new ArithmeticException("Negative BigInteger");
> 2724:         }

Please restore the original braces.

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

> 44:  * @author  Michael McCloskey
> 45:  * @author  Timothy Buktu
> 46:  * @author  Fabio Romano

In recent years we no longer add the @author tag. In fact, at some point we plan to remove them from the codebase.
Authorship is part of the git commits.

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

> 126:             intLen = 2;
> 127:             value[0] = hi;
> 128:             value[1] = (int) val;

Suggestion:

            value = new int[] {hi, (int) val}
            intLen = 2;

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

> 1914:      * @throws ArithmeticException if the value returned by {@code bitLength()}
> 1915:      * overflows the range of {@code int}.
> 1916:      * @return the integer square root of {@code this} and the remainder if needed

To emphasize, make use of `<em>` tags, not `<b>`.

By convention, a blank line precedes `@return`, which precedes `@throws` (see some public API examples).

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

> 1939: 
> 1940:             // Initial estimate is the square root of the unsigned long value.
> 1941:             long s = (long) Math.sqrt(x > 0 ? x : x + 0x1p64);

As a matter of simplification, the above cases can be collapsed to just this one. I don't think there's a real need to optimize for 0, [1, 4), `int`.

Also, there should be a proof that the code below is correct, as there are many roundings involved.

Suggestion:

            long s = (long) Math.sqrt(x >= 0 ? x : x + 0x1p64);

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

> 1965:         MutableBigInteger[] sqrtRem = x.sqrtRemZimmermann(x.intLen, needRemainder);
> 1966: 
> 1967:         // Unnormalize

This unnormalization code, as well as the one in the next method, requires a full explanation, perhaps in abstract, mathematical terms, to help understanding.

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

> 1995:         if (len == 2) { // Base case
> 1996:             long x = ((value[offset] & LONG_MASK) << 32) | (value[offset + 1] & LONG_MASK);
> 1997:             long s = (long) Math.sqrt(x > 0 ? x : x + 0x1p64);

Again, this needs a proof that doing so is always correct.

Suggestion:

            long s = (long) Math.sqrt(x >= 0 ? x : x + 0x1p64);

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

> 2018:          * The length is normalized to a mutiple of 4 because, in this way,
> 2019:          * the input can be always split in blocks of words without twiddling with bits.
> 2020:          */

What's substantially different here from the Bertot, Magaud, Zimmermann paper?
This is not explained in detail, so it is way harder to understand than the paper.

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

> 2019:          * the input can be always split in blocks of words without twiddling with bits.
> 2020:          */
> 2021:         final int limit = len;

The name `limit` reminds more an offset than a length.

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

> 2021:         final int limit = len;
> 2022:         final int excessInts = (-len) & 3;
> 2023:         len += excessInts; // len must be a multiple of 4

A comment like "this computes `excessInts = 4 * ceil(len / 4) - len`" or similar is welcome.

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

> 2028:         MutableBigInteger dividend = sr[1];
> 2029:         dividend.leftShift(blockBitLen);
> 2030:         dividend.add(getBlockZimmermann(1, len, limit, blockLen));

Maybe there's no need to use `add` here and just copying the block into the lower `blockLen` words is sufficient?

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

> 2038:         sqrt.add(q);
> 2039: 
> 2040:         MutableBigInteger chunk = u;

I don't get the need for `chunk`. It should be possible to use `u` directly.
Is it for readability? Then maybe use a more "mathematical" name.

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

> 2052: 
> 2053:                 rem.add(ONE);
> 2054:                 rem.subtract(twiceSqrt);

Shouldn't these be `rem + twiceSqrt - 1`?

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

> 2061:         }
> 2062: 
> 2063:         // Unnormalize

Again, this unnormalization code requires a full explanation.

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

> 2089:     }
> 2090: 
> 2091:     private MutableBigInteger getBlockZimmermann(int blockIndex, int len, int limit, int blockLen) {

Please add a comment on what this method is supposed to do.

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

PR Review: https://git.openjdk.org/jdk/pull/19710#pullrequestreview-2174704290
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675834855
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675836169
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675837722
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675842182
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675847407
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675848405
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675849681
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675851990
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675852854
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675853104
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675854097
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675854623
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675855041
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675856204
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1675856482

More information about the core-libs-dev mailing list