[Gmp-commit] /var/hg/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sat Jul 4 21:36:34 CEST 2026
details: /var/hg/gmp/rev/edb9a222aa4a
changeset: 18553:edb9a222aa4a
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Jul 04 21:32:18 2026 +0200
description:
Extract initial checks into mpn_perfect_square_trivial_p, by Seth Troisi
details: /var/hg/gmp/rev/8f16f154a9a1
changeset: 18554:8f16f154a9a1
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Jul 04 21:34:26 2026 +0200
description:
dded mpz_perfect_square_root, ny Seth Troisi
details: /var/hg/gmp/rev/bf12758d396e
changeset: 18555:bf12758d396e
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Jul 04 21:35:11 2026 +0200
description:
ChangeLog
details: /var/hg/gmp/rev/ac62fde50484
changeset: 18556:ac62fde50484
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Jul 04 21:35:55 2026 +0200
description:
Update a comment, by Seth Troisi
diffstat:
ChangeLog | 19 +++++++
Makefile.am | 3 +-
doc/gmp.texi | 17 +++++-
doc/tasks.html | 4 -
gmp-h.in | 3 +
gmp-impl.h | 3 +
mpn/generic/perfsqr.c | 23 +++++++-
mpz/Makefile.am | 2 +-
mpz/perfsqrt.c | 82 ++++++++++++++++++++++++++++++++
tests/mpz/t-perfsqr.c | 126 ++++++++++++++++++++++++++++++++++++++++++++-----
tune/speed.h | 2 +-
11 files changed, 254 insertions(+), 30 deletions(-)
diffs (truncated from 500 to 300 lines):
diff -r d4bbcd8fbd2b -r ac62fde50484 ChangeLog
--- a/ChangeLog Sat Jul 04 10:58:06 2026 +0200
+++ b/ChangeLog Sat Jul 04 21:35:55 2026 +0200
@@ -1,3 +1,17 @@
+2026-07-04 Seth Troisi <sethtroisi at google.com>
+
+ * mpn/generic/perfsqr.c: New function mpn_probab_perfect_square_p.
+ * gmp-impl.h: Declare its prototype.
+
+ * mpz/perfsqrt.c: New file, implementing mpz_perfect_square_root.
+ * mpz/Makefile.am (libmpz_la_SOURCES): Add the new file.
+ * Makefile.am (MPZ_OBJECTS): Update accordingly.
+ * gmp-h.in: Prototype for the new function.
+ * doc/gmp.texi: Document the new function.
+ * tests/mpz/t-perfsqr.c: Test it.
+
+ * doc/tasks.html:Remove mpz_sqrt_if_perfect_square, done.
+
2026-06-26 Marco Bodrato <marco.bodrato at protonmail.com>
* mpz/isetbit.c: New file, implementing mpz_init_setbit.
@@ -17,6 +31,11 @@
* mpn/generic/bsqrtinv.c: Higher order iteration step on half-limb.
* primesieve.c: Move a branch outside the loop.
+ * mpz/stronglucas.c: Use mpn_perfect_square_p instead of mpz_.
+ * mpz/millerrabin.c: Compute nm only when needed.
+ * mpn/generic/bsqrtinv.c: Higher order iteration step on half-limb.
+ * primesieve.c: Move a branch outside the loop.
+
2026-06-19 Marco Bodrato <marco.bodrato at protonmail.com>
* mpn/generic/perfpow.c (is_kth_power): Check only one possible
diff -r d4bbcd8fbd2b -r ac62fde50484 Makefile.am
--- a/Makefile.am Sat Jul 04 10:58:06 2026 +0200
+++ b/Makefile.am Sat Jul 04 21:35:55 2026 +0200
@@ -208,7 +208,8 @@
mpz/millerrabin$U.lo mpz/mod$U.lo mpz/mul$U.lo mpz/mul_2exp$U.lo \
mpz/mul_si$U.lo mpz/mul_ui$U.lo \
mpz/n_pow_ui$U.lo mpz/neg$U.lo mpz/nextprime$U.lo \
- mpz/out_raw$U.lo mpz/out_str$U.lo mpz/perfpow$U.lo mpz/perfsqr$U.lo \
+ mpz/out_raw$U.lo mpz/out_str$U.lo mpz/perfpow$U.lo \
+ mpz/perfsqr$U.lo mpz/perfsqrt$U.lo \
mpz/popcount$U.lo mpz/pow_ui$U.lo mpz/powm$U.lo mpz/powm_sec$U.lo \
mpz/powm_ui$U.lo mpz/primorial_ui$U.lo \
mpz/pprime_p$U.lo mpz/random$U.lo mpz/random2$U.lo \
diff -r d4bbcd8fbd2b -r ac62fde50484 doc/gmp.texi
--- a/doc/gmp.texi Sat Jul 04 10:58:06 2026 +0200
+++ b/doc/gmp.texi Sat Jul 04 21:35:55 2026 +0200
@@ -3606,6 +3606,16 @@
be perfect squares.
@end deftypefun
+ at deftypefun int mpz_perfect_square_root (mpz_t @var{rop}, const mpz_t @var{op})
+ at cindex Perfect square functions
+ at cindex Root testing functions
+Return non-zero and sets @var{rop} to the square root if @var{op} is a perfect
+square, i.e., if the square root of @var{op} is an integer. Under this
+definition both 0 and 1 are considered to be perfect squares and @var{rop} is
+set to @var{op} in both cases. If @var{op} is not a perfect square the value of
+ at var{rop} is undefined.
+ at end deftypefun
+
@need 2000
@node Number Theoretic Functions, Integer Comparisons, Integer Roots, Integer Functions
@@ -9254,9 +9264,10 @@
A significant fraction of non-squares can be quickly identified by checking
whether the input is a quadratic residue modulo small integers.
- at code{mpz_perfect_square_p} first tests the input mod 256, which means just
-examining the low byte. Only 44 different values occur for squares mod 256,
-so 82.8% of inputs can be immediately identified as non-squares.
+ at code{mpz_perfect_square_p}/@code{mpz_perfect_square_root} first tests the input
+mod 256, which means just examining the low byte. Only 44 different values
+occur for squares mod 256, so 82.8% of inputs can be immediately identified
+as non-squares.
On a 32-bit system similar tests are done mod 9, 5, 7, 13 and 17, for a total
99.25% of inputs identified as non-squares. On a 64-bit system 97 is tested
diff -r d4bbcd8fbd2b -r ac62fde50484 doc/tasks.html
--- a/doc/tasks.html Sat Jul 04 10:58:06 2026 +0200
+++ b/doc/tasks.html Sat Jul 04 21:35:55 2026 +0200
@@ -579,10 +579,6 @@
probably simplest to regard this as a compiler compatibility issue, and
leave it to users or sysadmins to ensure application and library code is
built the same.
-<li> <code>mpz_sqrt_if_perfect_square</code>: When
- <code>mpz_perfect_square_p</code> does its tests it calculates a square
- root and then discards it. For some applications it might be useful to
- return that root. Suggested by Jason Moxham.
<li> <code>mpz_get_ull</code>, <code>mpz_set_ull</code>,
<code>mpz_get_sll</code>, <code>mpz_get_sll</code>: Conversions for
<code>long long</code>. These would aid interoperability, though a
diff -r d4bbcd8fbd2b -r ac62fde50484 gmp-h.in
--- a/gmp-h.in Sat Jul 04 10:58:06 2026 +0200
+++ b/gmp-h.in Sat Jul 04 21:35:55 2026 +0200
@@ -975,6 +975,9 @@
__GMP_DECLSPEC int mpz_perfect_square_p (mpz_srcptr) __GMP_ATTRIBUTE_PURE;
#endif
+#define mpz_perfect_square_root __gmpz_perfect_square_root
+__GMP_DECLSPEC int mpz_perfect_square_root (mpz_ptr, mpz_srcptr);
+
#define mpz_popcount __gmpz_popcount
#if __GMP_INLINE_PROTOTYPES || defined (__GMP_FORCE_mpz_popcount)
__GMP_DECLSPEC mp_bitcnt_t mpz_popcount (mpz_srcptr) __GMP_NOTHROW __GMP_ATTRIBUTE_PURE;
diff -r d4bbcd8fbd2b -r ac62fde50484 gmp-impl.h
--- a/gmp-impl.h Sat Jul 04 10:58:06 2026 +0200
+++ b/gmp-impl.h Sat Jul 04 21:35:55 2026 +0200
@@ -4036,6 +4036,9 @@
#define PP_FIRST_OMITTED 3
#endif
+#define mpn_probab_perfect_square_p __MPN(probab_perfect_square_p)
+__GMP_DECLSPEC int mpn_probab_perfect_square_p (mp_srcptr, mp_size_t);
+
typedef struct
{
mp_limb_t d0, d1;
diff -r d4bbcd8fbd2b -r ac62fde50484 mpn/generic/perfsqr.c
--- a/mpn/generic/perfsqr.c Sat Jul 04 10:58:06 2026 +0200
+++ b/mpn/generic/perfsqr.c Sat Jul 04 21:35:55 2026 +0200
@@ -1,8 +1,12 @@
/* mpn_perfect_square_p(u,usize) -- Return non-zero if U is a perfect square,
zero otherwise.
-Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2012 Free Software
-Foundation, Inc.
+mpn_probab_perfect_square_p(u, usize) -- Returns non-zero if U not trivially
+disqualified from being a perfect square checks. Returns zero if impossible
+to be a perfect square.
+
+Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2012, 2026 Free
+Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -176,12 +180,10 @@
int
-mpn_perfect_square_p (mp_srcptr up, mp_size_t usize)
+mpn_probab_perfect_square_p (mp_srcptr up, mp_size_t usize)
{
ASSERT (usize >= 1);
- TRACE (gmp_printf ("mpn_perfect_square_p %Nd\n", up, usize));
-
/* The first test excludes 212/256 (82.8%) of the perfect square candidates
in O(1) time. */
{
@@ -217,6 +219,17 @@
according to their residues modulo small primes (or powers of
primes). See perfsqr.h. */
PERFSQR_MOD_TEST (up, usize);
+ return 1;
+}
+
+
+int
+mpn_perfect_square_p (mp_srcptr up, mp_size_t usize)
+{
+ TRACE (gmp_printf ("mpn_perfect_square_p %Nd\n", up, usize));
+
+ if (! mpn_probab_perfect_square_p (up, usize))
+ return 0;
/* For the third and last test, we finally compute the square root,
diff -r d4bbcd8fbd2b -r ac62fde50484 mpz/Makefile.am
--- a/mpz/Makefile.am Sat Jul 04 10:58:06 2026 +0200
+++ b/mpz/Makefile.am Sat Jul 04 21:35:55 2026 +0200
@@ -57,7 +57,7 @@
lucnum_ui.c lucnum2_ui.c lucmod.c mfac_uiui.c millerrabin.c \
mod.c mul.c mul_2exp.c mul_si.c mul_ui.c n_pow_ui.c neg.c nextprime.c \
oddfac_1.c \
- out_raw.c out_str.c perfpow.c perfsqr.c popcount.c pow_ui.c powm.c \
+ out_raw.c out_str.c perfpow.c perfsqr.c perfsqrt.c popcount.c pow_ui.c powm.c \
powm_sec.c powm_ui.c pprime_p.c prodlimbs.c primorial_ui.c random.c random2.c \
realloc.c realloc2.c remove.c roinit_n.c root.c rootrem.c rrandomb.c \
scan0.c scan1.c set.c set_d.c set_f.c set_q.c set_si.c set_str.c \
diff -r d4bbcd8fbd2b -r ac62fde50484 mpz/perfsqrt.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpz/perfsqrt.c Sat Jul 04 21:35:55 2026 +0200
@@ -0,0 +1,82 @@
+/* mpz_perfect_square_root(rop, op) -- Return non-zero if op is a perfect
+ square and sets rop to root, otherwise returns zero.
+
+Copyright 2026 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of either:
+
+ * the GNU Lesser General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your
+ option) any later version.
+
+or
+
+ * the GNU General Public License as published by the Free Software
+ Foundation; either version 2 of the License, or (at your option) any
+ later version.
+
+or both in parallel, as here.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received copies of the GNU General Public License and the
+GNU Lesser General Public License along with the GNU MP Library. If not,
+see https://www.gnu.org/licenses/. */
+
+#include "gmp-impl.h"
+
+int
+mpz_perfect_square_root (mpz_ptr rop, mpz_srcptr op)
+{
+ mp_size_t u_size = SIZ (op);
+
+ /* Handle <= 0 */
+ if (__GMP_UNLIKELY ( u_size <= 0))
+ {
+ /* Zero is a square with rop = 0 */
+ if ( u_size == 0)
+ {
+ SIZ(rop) = 0;
+ return 1;
+ }
+ /* Negatives are never perfect squares. */
+ return 0;
+ }
+
+ if (! mpn_probab_perfect_square_p (PTR (op), u_size))
+ return 0;
+
+ /* This is the precise size of sqrt(op) because leading limp is non-zero. */
+ mp_size_t rop_size = (SIZ (op) + 1) / 2;
+
+ /* mpn_sqrtrem doesn't allow sp == np */
+ if (rop == op)
+ {
+ TMP_DECL;
+ TMP_MARK;
+
+ mp_ptr rop_ptr = TMP_ALLOC_LIMBS (rop_size);
+ int res = ! mpn_sqrtrem (rop_ptr, NULL, PTR (op), u_size);
+
+ /* It might be better to always copy so the value in rop doesn't
+ depend on if the arguments are aliased or not. */
+ if (res)
+ {
+ MPN_COPY (PTR(rop), rop_ptr, rop_size);
+ SIZ(rop) = rop_size;
+ }
+
+ TMP_FREE;
+ return res;
+ }
+
+ /* Make sure rop has exact space for the square root. */
+ SIZ(rop) = rop_size;
+ return ! mpn_sqrtrem (MPZ_REALLOC (rop, rop_size), NULL, PTR (op), u_size);
+}
diff -r d4bbcd8fbd2b -r ac62fde50484 tests/mpz/t-perfsqr.c
--- a/tests/mpz/t-perfsqr.c Sat Jul 04 10:58:06 2026 +0200
+++ b/tests/mpz/t-perfsqr.c Sat Jul 04 21:35:55 2026 +0200
@@ -1,4 +1,4 @@
-/* Test mpz_perfect_square_p.
+/* Test mpz_perfect_square_p and mpz_perfect_square_root.
Copyright 2000-2002 Free Software Foundation, Inc.
@@ -26,10 +26,10 @@
#include "mpn/perfsqr.h"
-/* check_modulo() exercises mpz_perfect_square_p on squares which cover each
- possible quadratic residue to each divisor used within
- mpn_perfect_square_p, ensuring those residues aren't incorrectly claimed
- to be non-residues.
+/* check_modulo() exercises mpz_perfect_square_p/mpz_perfect_square_root on
+ squares which cover each possible quadratic residue to each divisor used
+ within mpn_perfect_square_p, ensuring those residues aren't incorrectly
+ claimed to be non-residues.
Each divisor is taken separately. It's arranged that n is congruent to 0
modulo the other divisors, 0 of course being a quadratic residue to any
@@ -45,11 +45,13 @@
static const unsigned long divisor[] = PERFSQR_DIVISORS;
unsigned long i, j;
- mpz_t alldiv, others, n;
+ mpz_t alldiv, others, n, root, rop;
mpz_init (alldiv);
More information about the gmp-commit
mailing list