On Mon, 15 Jul 2024 19:58:23 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: > > Optimized shift-and-add operations src/java.base/share/classes/java/math/MutableBigInteger.java line 1978: > 1976: * is either correct, or rounded up by one if the value is > too high > 1977: * and too close to the next perfect square. > 1978: */ Contrary to my previous believe and own experiments, I now think this code is incorrect. Let `long t = 3037000503L` and `long x = t * t`. The code computes `long s == 3037000502L`, an underestimate of the correct square root `t` by 1. Underestimates are neither detected nor corrected. Of course, the corresponding remainder `long r = x - s * s`, namely `r = 6074001005L`, is just barely too large as it does _not_ meet `r <= 2 * s`. ------------- PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1681033100
