On Fri, 12 Jul 2024 13:51:24 GMT, fabioromano1 <d...@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
