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