mpz_sqrt_if_perfect_square

[marco.bodrato at tutanota.com]

Ciao,

6 giu 2026, 08:45 da nisse at lysator.liu.se:

> Seth Troisi <braintwo at gmail.com> writes:
>
>> I changed the name.
>> Would mpn_probab_perfect_square_p (no ly) better match mpz_probab_prime?
>>
It would be more coherent, you are right.
Even if... I'm still not sure it really need to be a public function...
Why is it useful for a user of the library?


> It can be adjusted later (and I missed a bit of the structure when
>
I agree.

> If docs say that value is undefined, then I don't think it's worth an
> allocation to make it have some particular value.
>
I agree.

> If I understand your code correctly, then in the non-square case, rop
> will either be unchanged or get floor (sqrt(op)), depending on result of
>
Maybe, but it doesn't really matter.
A new implementation using a different algorithm may "undefine" the undefined result value in a different way :-)

I looked at the static function is_kth_power in mpn/generic/perfpow.c, and it uses mpn_bsqrtinv.
We should measure which approach is faster!

Currently, with tune/speed I measured:
$ build/tune/speed -r -s 100-2000 -p 100000000 -f 2 mpn_sqrtrem mpn_perfect_square_p
overhead 0.000000004 secs, precision 100000000 units of 7.71e-10 secs, CPU freq 1296.98 MHz
          mpn_sqrtrem mpn_perfect_square_p
100      #0.000004973        1.1300
200      #0.000013476        1.1107
400      #0.000039413        1.0958
800      #0.000119246        1.1256
1600     #0.000362528        1.1040

Does that mean that mpn_perfect_square_p is consistently 10% slower than computing the root and the full reminder?
Ĝis,
m