RFR: 8334755: Asymptotically faster implementation of square root algorithm [v28]

[fabioromano1]

On Wed, 17 Jul 2024 13:48:59 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> 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`.
>
> In fact, if you run this code:
> `long limit = 1L << 32;
>  for (long n = 0; n < limit; n++) {
>       long x = n * n;
>       if (n != (long) Math.sqrt(x >= 0 ? x : x + 0x1p64)) {
>           System.out.println(n);
>       }
> }`
> 
> now you find a lot of counterexamples. The question is: why, until recently, if I did run the same code I could not find a counterexample?

I hope these errors are not due to an implementation change in the virtual machine instructions...

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1681105179