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

[Raffaello Giulietti]

On Fri, 12 Jul 2024 13:51:24 GMT, fabioromano1 <duke at openjdk.org> wrote:

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1967:
>> 
>>> 1965:         MutableBigInteger[] sqrtRem = x.sqrtRemZimmermann(x.intLen, needRemainder);
>>> 1966: 
>>> 1967:         // Unnormalize
>> 
>> This unnormalization code, as well as the one in the next method, requires a full explanation, perhaps in abstract, mathematical terms, to help understanding.
>
> The full explanation for the unnormalization is in the second paper, "A proof of GMP square root", par. 3.2 at page 11.

Well, I have to compare that section, which is clear to me, with the code again.

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 1997:
>> 
>>> 1995:         if (len == 2) { // Base case
>>> 1996:             long x = ((value[offset] & LONG_MASK) << 32) | (value[offset + 1] & LONG_MASK);
>>> 1997:             long s = (long) Math.sqrt(x > 0 ? x : x + 0x1p64);
>> 
>> Again, this needs a proof that doing so is always correct.
>> 
>> Suggestion:
>> 
>>             long s = (long) Math.sqrt(x >= 0 ? x : x + 0x1p64);
>
> Here there's no need to modify `x > 0` with `x >= 0`.

Sure, but again: changing `>` to `>=` makes the code correct even for `0`.

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 2020:
>> 
>>> 2018:          * The length is normalized to a mutiple of 4 because, in this way,
>>> 2019:          * the input can be always split in blocks of words without twiddling with bits.
>>> 2020:          */
>> 
>> What's substantially different here from the Bertot, Magaud, Zimmermann paper?
>> This is not explained in detail, so it is way harder to understand than the paper.
>
> In the paper, the input is normalized to an even number of words... but this is not done in the pseudocode, since the pseudocode assumes that the input is already normalized, so actually there's no substantial difference...

Yes, normalization is done in §3.2. Will have another look.

>> src/java.base/share/classes/java/math/MutableBigInteger.java line 2021:
>> 
>>> 2019:          * the input can be always split in blocks of words without twiddling with bits.
>>> 2020:          */
>>> 2021:         final int limit = len;
>> 
>> The name `limit` reminds more an offset than a length.
>
> The solution can be either to change its name, or to use it as an offset, but this second involves to modify the logic of the code, with higher risk of introducing errors.

I suggest changing the name: `maxLen`, `hiLen`, something similar.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1676036185
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1676037890
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1676039724
PR Review Comment: https://git.openjdk.org/jdk/pull/19710#discussion_r1676040186