On Wed, 17 Jul 2024 13:15:17 GMT, Raffaello Giulietti <rgiulie...@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
