stronglucas.c

[Marco Bodrato]

Ciao,

Il Mer, 18 Maggio 2022 7:48 am, Niels Möller ha scritto:
> Seth Troisi <braintwo at gmail.com> writes:
>> I was reading the stronglucas code

Great!

>> diff -r 970b7221873f mpz/stronglucas.c

>>      /* n is odd, to possibly be a square, n % 8 = 1 is needed. */
>> -    if (((*PTR (n) & 6) == 0) && UNLIKELY (mpz_perfect_square_p (n)))
>> +    if (((*PTR (n) & 7) == 1) && UNLIKELY (mpz_perfect_square_p (n)))
>>        return 0; /* A square is composite. */

>> Technically n/x should be odd per the function comment but IMO this
>> improves readability by having the "n % 8 = 1" in the nearer comment
>> match the code.

> I think the way it's currently written is a micro optimization, testing

> That said, I don't think this code is that performance critical, so
> saving a single instruction doesn't matter much. I agree your change
> improves readability a bit.

Shall we remove a (micro) optimization, or shall we improve the comment?

Anyway, the whole "((*PTR (n) & 6) == 0) &&" code is only an optimization,
the first check done by the function mpz_perfect_square_p is based on the
lowest bits. Should we avoid to repeat the check here and simply call the
function?

>> It's also possible lines 122-124 should also be indented
>
> Indentation looks right to me, at the current place. But perhaps more
> consistent with nearby code if comments are moved below the "else if"
> line (and then indented accordingly for that location).

line 122
  /* (2^24 - 1) | (2^{GMP_NUMB_BITS*3/4} - 1)	*/
is indented as line 97;
  /* (2^12 - 1) | (2^{GMP_NUMB_BITS*3/4} - 1)	*/
123 as 99.
Those comments should explain what happens with the given GMP_NUMB_BITS
values.

But I agree, there should also be a comment after the "else if",
explaining how the check for D=17 works.



There are also other comments that should be improved.
The comment to the function (line 80) reads:
/* Requires GCD (x,6) = 1.*/

Inside the code included by
#if GMP_NUMB_BITS % 16 == 0
we have (line 100)
  ASSERT (g % 3 != 0 && g % 5 != 0 && g % 7 != 0);

but I fear that the code actually assumes also
 g % 11 != 0 && g % 13 != 0 && g % 17 != 0

Not a problem, with the current use in the library (this code is called
after some trial division check), but it is more difficult to read the
code if the comments are not correct.

Ĝis,
m