mpz_sqrt_if_perfect_square

[Seth Troisi]

Thanks for the continued reviewing

On Fri, Jun 5, 2026 at 11:08 AM Niels Möller <nisse at lysator.liu.se> wrote:

> Seth Troisi <braintwo at gmail.com> writes:
>
> > New patch using mpz_perfect_square_root name
> > + at deftypefun int mpn_perfect_square_trivial_p (const mp_limb_t
> *@var{s1p}, mp_size_t @var{n})
> > +Return non-zero iff @{@var{s1p}, @var{n}@} passes preliminary perfect
> square checks.
> > +The most significant limb of the input @{@var{s1p}, @var{n}@} must be
> non-zero.
> >  @end deftypefun
>
> Another function that needs the right name... I don't think "trivial" is
> the right attribute. Maybe mpn_probably_perfect_square_p (even though
> it's not really probabilistic) for consistency with probably_prime_p. We
> need something to convey that it's fast and cheap (and not totally
> accurate). Regardless of name, maybe say clarly that if it returns
> false, the input is certainly not a square.
>
>
I changed the name.
Would mpn_probab_perfect_square_p (no ly) better match mpz_probab_prime?


> >  @deftypefun void mpn_and_n (mp_limb_t *@var{rp}, const mp_limb_t
> *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{n})
> > @@ -9250,9 +9263,10 @@
> >  A significant fraction of non-squares can be quickly identified by
> checking
> >  whether the input is a quadratic residue modulo small integers.
> ...
> I think these docs should be attached to mpn_perfect_square_trivial_p.
>

I'd prefer not to be the person making the decision on where these notes
(currently in algorithm) go.
Would it be reasonable for any changes to be made after this patch is
merged?


> Not sure this inner  __GMP_UNLIKELY is helpful, I'd leave to the branch
> predictor to find out if zero or negative is more common.
>

Done

Clearer with mp_size_t instead of int. And I think it may be worth a comment
> saying that this size is precise (limb rop_size - 1 will always be
> non-zero).
>

Done


> > +  /* mpn_sqrtrem doesn't allow sp == np */
> > +  if (rop == u)
> ...

> +      /* It might be better to always copy so the value in rop
> > +         is more determistic. */
>
> Unless I'm missing something, the current code leaves rop unchanged when
> res == 0? That seems deterministic enough.
>

I updated the comment to
      /* It might be better to always copy so the value in rop doesn't
         depend on if the arguments are aliased or not. */

I could always allocate the temporary but I think that's less efficient


> > +      if (res)
> > +        {
> > +          MPN_COPY (PTR(rop), rop_ptr, rop_size);
> > +          SIZ(rop) = rop_size;
> > +        }
> > +
> > +      TMP_FREE;
> > +      return res;
> > +    }
> > +
> > +  /* Make sure rop has space for the square root. */
> > +  MPZ_REALLOC(rop, rop_size);
> > +
> > +  int res = ! mpn_sqrtrem (PTR (rop), NULL, PTR (u), u_size);
>
> I think MPZ_REALLOC returns the pointer, so you could write this as
>
>      int res = ! mpn_sqrtrem (MPZ_REALLOC (rop, rop_size), NULL, PTR (u),
> u_size);
>
> Or do you think it is clearer with MPZ_REALLOC more separated?
>
> > +  if (res)
> > +    {
> > +      SIZ(rop) = rop_size;
> > +    }
> > +  return res;
>
> In the non-square case, I think there's a risk that we produce a rop
> that isn't normalized. To keep things simple, maybe just set SIZ(rop) =
> 0 in that case? I.e.,
>

I changed this to always set SIZ (rop) = rop_size so rop is the return of
sqrt(op).

As an interesting thought If the contract was inverted (return zero if
perfect square) This could return
0: perfect square, rop set to sqrt
1: not square, rop set to sqrt
2: not square, rop not set

I guess if someone needs this functionality right now they can set rop to
any negative sentinel.


>
>   SIZ (rop) = res ? rop_size : 0;
>   return res;
>
> Regards,
> /Niels
>
> --
> Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
> Internet email is subject to wholesale government surveillance.
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mpz_perfect_square_root.PATCH
Type: application/octet-stream
Size: 17549 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20260605/70512aac/attachment-0001.obj>