On Thu, 18 Jul 2024 13:09:08 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: > > Uniforming the computation of long values' square root src/java.base/share/classes/java/math/MutableBigInteger.java line 2032: > 2030: s = s1; > 2031: } > 2032: return s; Experimentally, the following seems a bit faster. In some cases, it avoids a full multiplication, some updates, and has one less test. I hope it is correct as well ;-) Suggestion: long s = (long) Math.sqrt(x >= 0 ? x : x + 0x1p64); long s2 = s * s; // overflows iff s = 2^32 if (s == 1L << 32 || Long.compareUnsigned(x, s2) < 0) { return s - 1; } if (Long.compareUnsigned(x, s2 + 2 * s) <= 0) { // x < (s + 1)^2 return s; } return s + 1; ------------- PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1683053330
