mpz_sqrt_if_perfect_square

[Seth Troisi]

I'm fixed mpz_perfect_square(x, x), I have to detect root == op because
mpn_sqrtrem requires r1p != sp.

Everyone loves naming, these are my suggestions. Any of these can have the
_p predicate suffix attached or not.
mpz_sqrt_exact_p <- My favorite
mpz_sqrt_p
mpz_sqrt_if_perfect_square
mpz_perfect_square_with_root
mpz_perfect_square_root



On Tue, Jun 2, 2026 at 10:55 PM <marco.bodrato at tutanota.com> wrote:

> Ciao,
>
> 3 giu 2026, 05:55 da braintwo at gmail.com:
>
> The top limb could be zero, right?
>
> The docs say "The most significant limb of @{@var{s1p}, @var{n}@} must be
> non-zero."
> I believe this makes the size of sqrt(u) exactly (n+1)/ 2 for any perfect
> square.
>
> I agree.
>
> I'm was unsure how much I should optimize for an extra memory allocation vs
> clobbering rop.
>
> Well, actually an undefined return value was not really a problem IMO. We
> already have:
> @deftypefun int mpz_invert (mpz_t @var{rop}, const mpz_t @var{op1}, const
> mpz_t @var{op2})
> [...]  If an inverse doesn't
> exist the return value is zero and @var{rop} is undefined.  The behaviour
> of
> this function is undefined when @var{op2} is zero.
> @end deftypefun
>
> Anyway we have to pay attention to another side.
> For mpz_ (and mpq_, and mpf_) functions, the manual promises
> "GMP lets you use the same variable for both input and output in one call."
> This means that mpz_perfect_square(x, x) should work.
>
> I went with 1 and added mpn_perfect_square_trivial_p along with docs in to
> gmp.texi, it might benefit from a better name
>
> We don't need to document internal functions...
> Mark it as static if it is not used outside the same file.
> Or, if it is used internally, move its prototype from gmp-h.in to
> gmp-impl.h
>
> As some extra due-diligence I added a test for -4, 0, 1 to t-perfsqr and
> ran speed before and after (both in debug mode) and didn't see any
> regression.
>
> About speed, look at the code in tune/speed.h . It only tests the
> "worst case (larger prime) for perfect_square", i.e. squares.
> I mean, tune/speed will not detect if the new code is slower in detecting
> non-squares.
>
> Currently, I only glanced at your code, but I'd suggest two small things:
>  - let's choose a better name (the function returns the root, not the
> square);
>  - in the main branch of mpz_perfect_square we shoud have a single
> UNLIKELY branch: <=0.
>
> Ĝis,
> m
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mpn_perfect_square.PATCH
Type: application/octet-stream
Size: 14932 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20260603/05030b13/attachment.obj>