[Gmp-commit] /var/hg/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sat Nov 16 07:49:46 UTC 2019
details: /var/hg/gmp/rev/e125bf760fdd
changeset: 17960:e125bf760fdd
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Nov 16 08:18:13 2019 +0100
description:
tune/: tune/speed support for mpn_perfect_{power,square}_p (by Seth Troisi)
details: /var/hg/gmp/rev/8aa3b936c707
changeset: 17961:8aa3b936c707
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Nov 16 08:19:39 2019 +0100
description:
tune/: tune/speed support for mpz_nextprime (by Seth Troisi)
details: /var/hg/gmp/rev/402400a0dc12
changeset: 17962:402400a0dc12
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Nov 16 08:19:51 2019 +0100
description:
ChangeLog
details: /var/hg/gmp/rev/0a7bccdcda14
changeset: 17963:0a7bccdcda14
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sat Nov 16 08:48:59 2019 +0100
description:
tune: Small optimisations to recent changes.
diffstat:
ChangeLog | 11 ++++++
tune/common.c | 20 +++++++++++-
tune/speed.c | 8 ++++-
tune/speed.h | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
4 files changed, 133 insertions(+), 3 deletions(-)
diffs (226 lines):
diff -r 5042923d8c45 -r 0a7bccdcda14 ChangeLog
--- a/ChangeLog Sun Nov 10 11:07:27 2019 +0100
+++ b/ChangeLog Sat Nov 16 08:48:59 2019 +0100
@@ -1,3 +1,14 @@
+2019-11-16 Seth Troisi <sethtroisi at google.com>
+
+ * tune/common.c (speed_mpn_perfect_power_p): New function.
+ (speed_mpn_perfect_power_p): New function.
+ * tune/speed.h: Declare both.
+ * tune/speed.c (routine): Add mpn_perfect_{power,square}_p.
+
+ * tune/common.c (speed_mpz_nextprime): New function.
+ * tune/speed.h: Declare it.
+ * tune/speed.c (routine): Add mpz_nextprime.
+
2019-11-09 Marco Bodrato <bodrato at mail.dm.unipi.it>
* tune/speed.c (routine_t): Add R flago to mpz_powm
diff -r 5042923d8c45 -r 0a7bccdcda14 tune/common.c
--- a/tune/common.c Sun Nov 10 11:07:27 2019 +0100
+++ b/tune/common.c Sat Nov 16 08:48:59 2019 +0100
@@ -1,6 +1,6 @@
/* Shared speed subroutines.
-Copyright 1999-2006, 2008-2017 Free Software Foundation, Inc.
+Copyright 1999-2006, 2008-2017, 2019 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -1763,6 +1763,11 @@
SPEED_ROUTINE_MPN_GCD_22 (mpn_gcd_22);
}
+double
+speed_mpz_nextprime (struct speed_params *s)
+{
+ SPEED_ROUTINE_MPZ_NEXTPRIME (mpz_nextprime);
+}
double
speed_mpz_jacobi (struct speed_params *s)
@@ -1822,6 +1827,19 @@
double
+speed_mpn_perfect_power_p (struct speed_params *s)
+{
+ SPEED_ROUTINE_MPN_PERFECT_POWER (mpn_perfect_power_p);
+}
+
+double
+speed_mpn_perfect_square_p (struct speed_params *s)
+{
+ SPEED_ROUTINE_MPN_PERFECT_SQUARE (mpn_perfect_square_p);
+}
+
+
+double
speed_mpz_fac_ui (struct speed_params *s)
{
SPEED_ROUTINE_MPZ_FAC_UI (mpz_fac_ui);
diff -r 5042923d8c45 -r 0a7bccdcda14 tune/speed.c
--- a/tune/speed.c Sun Nov 10 11:07:27 2019 +0100
+++ b/tune/speed.c Sat Nov 16 08:48:59 2019 +0100
@@ -1,6 +1,6 @@
/* Speed measuring program.
-Copyright 1999-2003, 2005, 2006, 2008-2018 Free Software Foundation, Inc.
+Copyright 1999-2003, 2005, 2006, 2008-2019 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -313,6 +313,9 @@
#if 0
{ "mpn_gcdext_lehmer", speed_mpn_gcdext_lehmer },
#endif
+
+ { "mpz_nextprime", speed_mpz_nextprime },
+
{ "mpz_jacobi", speed_mpz_jacobi },
{ "mpn_jacobi_base", speed_mpn_jacobi_base },
{ "mpn_jacobi_base_1", speed_mpn_jacobi_base_1 },
@@ -403,6 +406,9 @@
{ "mpn_sqrt", speed_mpn_sqrt },
{ "mpn_root", speed_mpn_root, FLAG_R },
+ { "mpn_perfect_power_p", speed_mpn_perfect_power_p, },
+ { "mpn_perfect_square_p", speed_mpn_perfect_square_p, },
+
{ "mpn_fib2_ui", speed_mpn_fib2_ui, FLAG_NODATA },
{ "mpz_fib_ui", speed_mpz_fib_ui, FLAG_NODATA },
{ "mpz_fib2_ui", speed_mpz_fib2_ui, FLAG_NODATA },
diff -r 5042923d8c45 -r 0a7bccdcda14 tune/speed.h
--- a/tune/speed.h Sun Nov 10 11:07:27 2019 +0100
+++ b/tune/speed.h Sat Nov 16 08:48:59 2019 +0100
@@ -1,6 +1,7 @@
/* Header for speed and threshold things.
-Copyright 1999-2003, 2005, 2006, 2008-2016 Free Software Foundation, Inc.
+Copyright 1999-2003, 2005, 2006, 2008-2017, 2019 Free Software
+Foundation, Inc.
This file is part of the GNU MP Library.
@@ -342,6 +343,8 @@
double speed_mpn_rootrem (struct speed_params *);
double speed_mpn_sqrt (struct speed_params *);
double speed_mpn_root (struct speed_params *);
+double speed_mpn_perfect_power_p (struct speed_params *);
+double speed_mpn_perfect_square_p (struct speed_params *);
double speed_mpn_sub_n (struct speed_params *);
double speed_mpn_sub_1 (struct speed_params *);
double speed_mpn_sub_1_inplace (struct speed_params *);
@@ -404,6 +407,7 @@
double speed_mpz_fib2_ui (struct speed_params *);
double speed_mpz_init_clear (struct speed_params *);
double speed_mpz_init_realloc_clear (struct speed_params *);
+double speed_mpz_nextprime (struct speed_params *);
double speed_mpz_jacobi (struct speed_params *);
double speed_mpz_lucnum_ui (struct speed_params *);
double speed_mpz_lucnum2_ui (struct speed_params *);
@@ -3160,6 +3164,47 @@
return t; \
}
+/* Calculate nextprime(n) for random n of s->size bits (not limbs). */
+#define SPEED_ROUTINE_MPZ_NEXTPRIME(function) \
+ { \
+ unsigned i, j; \
+ mpz_t wp, n; \
+ double t; \
+ \
+ SPEED_RESTRICT_COND (s->size >= 10); \
+ \
+ mpz_init (wp); \
+ mpz_init_set_n (n, s->xp, s->size); \
+ /* limit to s->size bits, as this function is very slow */ \
+ mpz_tdiv_r_2exp (n, n, s->size); \
+ /* set high bits so operand and result are genaral s->size bits */ \
+ mpz_setbit (n, s->size - 1); \
+ mpz_clrbit (n, s->size - 2); \
+ \
+ speed_starttime (); \
+ i = s->reps; \
+ do \
+ { \
+ /* nextprime timing is variable, so average over many calls */ \
+ j = SPEED_BLOCK_SIZE - 1; \
+ /* starts on random, after measures prime to next prime */ \
+ function (wp, n); \
+ do \
+ { \
+ function (wp, wp); \
+ } \
+ while (--j != 0); \
+ } \
+ while (--i != 0); \
+ t = speed_endtime (); \
+ \
+ mpz_clear (wp); \
+ mpz_clear (n); \
+ \
+ s->time_divisor = SPEED_BLOCK_SIZE; \
+ return t; \
+ }
+
#define SPEED_ROUTINE_MPZ_JACOBI(function) \
{ \
mpz_t a, b; \
@@ -3430,6 +3475,56 @@
}
+/* Calculate worst case for perfect_power
+ Worst case is multiple prime factors larger than trial div limit. */
+#define SPEED_ROUTINE_MPN_PERFECT_POWER(function) \
+ { \
+ mpz_t r; \
+ unsigned i, power; \
+ double t; \
+ \
+ SPEED_RESTRICT_COND (s->size >= 10); \
+ \
+ mpz_init (r); \
+ power = s->size * GMP_NUMB_BITS / 17; \
+ mpz_ui_pow_ui(r, (1 << 17) - 1, power - 1); \
+ mpz_mul_ui(r, r, (1 << 16) + 1); /* larger than 1000th prime */ \
+ \
+ speed_starttime (); \
+ i = s->reps; \
+ do \
+ function (PTR(r), SIZ(r)); \
+ while (--i != 0); \
+ t = speed_endtime (); \
+ \
+ mpz_clear (r); \
+ return t; \
+ }
+
+/* Calculate worst case (larger prime) for perfect_square */
+#define SPEED_ROUTINE_MPN_PERFECT_SQUARE(function) \
+ { \
+ mpz_t r; \
+ unsigned i; \
+ double t; \
+ \
+ SPEED_RESTRICT_COND (s->size >= 2); \
+ mpz_init_set_n (r, s->xp, s->size / 2); \
+ mpz_setbit (r, s->size * GMP_NUMB_BITS / 2 - 1); \
+ mpz_mul (r, r, r); \
+ \
+ speed_starttime (); \
+ i = s->reps; \
+ do \
+ function (PTR(r), SIZ(r)); \
+ while (--i != 0); \
+ t = speed_endtime (); \
+ \
+ mpz_clear (r); \
+ return t; \
+ }
+
+
/* s->size controls the number of limbs in the input, s->r is the base, or
decimal by default. */
#define SPEED_ROUTINE_MPN_GET_STR(function) \
More information about the gmp-commit
mailing list