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

[Raffaello Giulietti]

On Thu, 18 Jul 2024 14:39:16 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1973:
>> 
>>> 1971: 
>>> 1972:             /* For every long value s in [0, 2^32) such that x == s * s,
>>> 1973:              * it is true that s == Math.round(Math.sqrt(x >= 0 ? x : x + 0x1p64)),
>> 
>> To reinforce this claim, I suggest to add a test for all perfect squares.
>
> I did it, although I'm afraid it takes up too much running time due to the overhead of BigInteger's wrapping...

I mean only restricted to unsigned `long` perfect squares, something like the following, but written as a proper test


        long i = 0;
        for (; i < 1L << 32; ++i) {
            long x = i * i;
            long s = (long) Math.sqrt(x >= 0 ? x : x + 0x1p64);
            if (!(s + 1 == i || s == i)) {
                System.out.format("oops... i=%d, but s=%d%n", i, s);
                System.exit(1);
            }
        }

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

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