From ad7bd8ca59f4d6614e6bc980f931c69a581fee7e Mon Sep 17 00:00:00 2001
From: Marco Bodrato <bodrato@mail.dm.unipi.it>
Date: Fri, 30 Dec 2016 07:56:52 +0100
Subject: tune/: support mpz_invert

---
 tune/common.c | 41 +++++++++++++++++++++++++++++++++++++++++
 tune/speed.c  |  1 +
 tune/speed.h  |  1 +
 3 files changed, 43 insertions(+)

(limited to 'tune')

diff --git a/tune/common.c b/tune/common.c
index a794aafe6..41a1860da 100644
--- a/tune/common.c
+++ b/tune/common.c
@@ -2039,6 +2039,47 @@ speed_mpz_add (struct speed_params *s)
 }
 
 
+/* An inverse (s->r) or (s->size)/2 modulo s->size limbs */
+
+double
+speed_mpz_invert (struct speed_params *s)
+{
+  mpz_t     a, m, r;
+  mp_size_t k;
+  unsigned  i;
+  double    t;
+
+  if (s->r == 0)
+    k = s->size/2;
+  else if (s->r < GMP_LIMB_HIGHBIT)
+    k = s->r;
+  else /* s->r < 0 */
+    k = s->size - (-s->r);
+
+  SPEED_RESTRICT_COND (k > 0 && k <= s->size);
+
+  mpz_init_set_n (m, s->yp, s->size);
+  mpz_setbit (m, 0);	/* force m to odd */
+
+  mpz_init_set_n (a, s->xp, k);
+
+  mpz_init (r);
+  while (mpz_invert (r, a, m) == 0)
+    mpz_add_ui (a, a, 1);
+
+  speed_starttime ();
+  i = s->reps;
+  do
+    mpz_invert (r, a, m);
+  while (--i != 0);
+  t = speed_endtime ();
+
+  mpz_clear (r);
+  mpz_clear (a);
+  mpz_clear (m);
+  return t;
+  }
+
 /* If r==0, calculate binomial(size,size/2),
    otherwise calculate binomial(size,r). */
 
diff --git a/tune/speed.c b/tune/speed.c
index b49d5abf6..d7bec7afc 100644
--- a/tune/speed.c
+++ b/tune/speed.c
@@ -403,6 +403,7 @@ const struct routine_t {
   { "mpz_lucnum2_ui",    speed_mpz_lucnum2_ui, FLAG_NODATA },
 
   { "mpz_add",           speed_mpz_add              },
+  { "mpz_invert",        speed_mpz_invert,   FLAG_R_OPTIONAL },
   { "mpz_bin_uiui",      speed_mpz_bin_uiui, FLAG_NODATA | FLAG_R_OPTIONAL },
   { "mpz_bin_ui",        speed_mpz_bin_ui,   FLAG_NODATA | FLAG_R_OPTIONAL },
   { "mpz_fac_ui",        speed_mpz_fac_ui,   FLAG_NODATA   },
diff --git a/tune/speed.h b/tune/speed.h
index dd95372c9..c8c01093c 100644
--- a/tune/speed.h
+++ b/tune/speed.h
@@ -384,6 +384,7 @@ double speed_MPN_ZERO (struct speed_params *);
 double speed_mpq_init_clear (struct speed_params *);
 
 double speed_mpz_add (struct speed_params *);
+double speed_mpz_invert (struct speed_params *);
 double speed_mpz_bin_uiui (struct speed_params *);
 double speed_mpz_bin_ui (struct speed_params *);
 double speed_mpz_fac_ui (struct speed_params *);
-- 
cgit v1.2.1