On Wed, 31 Jul 2024 18:52:12 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: > > 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
