mpz_sqrt_if_perfect_square

[Seth Troisi]

On Tue, Jun 9, 2026 at 10:29 AM <marco.bodrato at tutanota.com> wrote:

> 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?
>

I've removed it from gmp-h.in and the docs.


> 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?
>

Speed.h has this comment for SPEED_ROUTINE_MPN_PERFECT_SQUARE

/* Calculate worst case (larger prime) for perfect_square */

If I change the loop body in increment r by 1 on each loop I get these
results

$ ./tune/speed  -r -s 100-2000 -p 100000000 -f 2 mpn_sqrtrem
mpn_perfect_square_p
overhead 0.000000001 secs, precision 100000000 units of 2.51e-10 secs, CPU
freq 3980.51 MHz
          mpn_sqrtrem mpn_perfect_square_p
100       0.000001297       #0.0110
200       0.000003405       #0.0075
400       0.000010291       #0.0056
800       0.000030102       #0.0051
1600      0.000090388       #0.0044



> Ĝis,
> m
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mpz_perfect_square_root.PATCH
Type: application/octet-stream
Size: 16719 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20260627/ef7cf763/attachment.obj>