On Tue, 9 Jul 2024 20:06:40 GMT, fabioromano1 <d...@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
