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

[fabioromano1]

On Wed, 17 Jul 2024 13:15:17 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> 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`.

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?

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

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