[Gmp-commit] /var/hg/gmp: tune/modlinv.c: Add measurable binvert_limb_sec bin...
mercurial at gmplib.org
mercurial at gmplib.org
Thu Jul 2 14:46:47 CEST 2026
details: /var/hg/gmp/rev/70fcc78764e4
changeset: 18549:70fcc78764e4
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Jul 02 14:13:11 2026 +0200
description:
tune/modlinv.c: Add measurable binvert_limb_sec binvert_limb_pipe
diffstat:
tune/modlinv.c | 130 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
tune/speed.c | 3 +
tune/speed.h | 3 +
3 files changed, 134 insertions(+), 2 deletions(-)
diffs (181 lines):
diff -r 1d1aff591461 -r 70fcc78764e4 tune/modlinv.c
--- a/tune/modlinv.c Thu Jul 02 07:58:25 2026 +0200
+++ b/tune/modlinv.c Thu Jul 02 14:13:11 2026 +0200
@@ -1,7 +1,7 @@
/* Alternate implementations of binvert_limb to compare speeds. */
/*
-Copyright 2000, 2002 Free Software Foundation, Inc.
+Copyright 2000, 2002, 2022 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -29,11 +29,122 @@
GNU Lesser General Public License along with the GNU MP Library. If not,
see https://www.gnu.org/licenses/. */
-#include <stdio.h>
#include "gmp-impl.h"
#include "longlong.h"
#include "speed.h"
+#define binvert_limb_uintfast(inv,n) \
+ do { \
+ mp_limb_t __n = (n); \
+ mp_limb_t __inv; \
+ UHWtype __inv8; \
+ ASSERT ((__n & 1) == 1); \
+ \
+ __inv8 = binvert_limb_table[(__n & 0xff)/2]; /* 8 */ \
+ if (GMP_NUMB_BITS > 16) { \
+ UHWtype __inv16 = 2 * __inv8 - __inv8 * __inv8 * __n; \
+ if (GMP_NUMB_BITS > 32) { \
+ UHWtype __inv32 = 2 * __inv16 - __inv16 * __inv16 * __n; \
+ __inv = 2*(mp_limb_t)__inv32 - (mp_limb_t)__inv32*__inv32*__n; \
+ } else {\
+ __inv = 2*(mp_limb_t)__inv16 - (mp_limb_t)__inv16*__inv16*__n; \
+ }; \
+ } else {\
+ __inv = 2 * (mp_limb_t)__inv8 - (mp_limb_t)__inv8 * __inv8 * __n; \
+ }; \
+ \
+ if (GMP_NUMB_BITS > 64) \
+ { \
+ int __invbits = 64; \
+ do { \
+ __inv = 2 * __inv - __inv * __inv * __n; \
+ __invbits *= 2; \
+ } while (__invbits < GMP_NUMB_BITS); \
+ } \
+ \
+ ASSERT ((__inv * __n & GMP_NUMB_MASK) == 1); \
+ (inv) = __inv & GMP_NUMB_MASK; \
+ } while (0)
+
+/* A (not exact) copy of the binvert function contained in
+ mpn/generic/sec_powm.c .
+ */
+
+static mp_limb_t
+sec_binvert_limb (mp_limb_t n)
+{
+ mp_limb_t inv, t;
+ ASSERT ((n & 1) == 1);
+ /* 3 + 2 -> 5 */
+ UHWtype th, invh = n + (((n + 1) << 1) & 0x18);
+ /* UHWtype th, invh = (n * 3) ^ 2; */
+
+ th = n * invh;
+#if GMP_NUMB_BITS <= 10
+ /* 5 x 2 -> 10 */
+ inv = 2 * invh - invh * th;
+#else /* GMP_NUMB_BITS > 10 */
+ /* 5 x 2 + 2 -> 12 */
+ invh = 2 * invh - invh * th + ((invh<<10)&-(th&(1<<5)));
+#endif /* GMP_NUMB_BITS <= 10 */
+
+ if (GMP_NUMB_BITS > 12)
+ {
+ t = n * invh - 1;
+ if (GMP_NUMB_BITS <= 36)
+ {
+ /* 12 x 3 -> 36 */
+ inv = invh + invh * t * (t - 1);
+ }
+ else /* GMP_NUMB_BITS > 36 */
+ {
+ mp_limb_t t2 = t * t;
+#if GMP_NUMB_BITS <= 60
+ /* 12 x 5 -> 60 */
+ inv = invh + invh * (t2 + 1) * (t2 - t);
+#else /* GMP_NUMB_BITS > 60 */
+ /* 12 x 5 + 4 -> 64 */
+ inv = invh * ((t2 + 1) * (t2 - t) + 1 - ((t<<48)&-(t&(1<<12))));
+
+ /* 64 -> 128 -> 256 -> ... */
+ for (int todo = (GMP_NUMB_BITS - 1) >> 6; todo != 0; todo >>= 1)
+ inv = 2 * inv - inv * inv * n;
+#endif /* GMP_NUMB_BITS <= 60 */
+ }
+ }
+
+ ASSERT ((inv * n & GMP_NUMB_MASK) == 1);
+ return inv & GMP_NUMB_MASK;
+}
+
+#define binvert_limb_sec(inv,n) inv = sec_binvert_limb (n)
+
+/* Like the standard version in gmp-impl.h, but with a different path
+ for bit sizes larger than 32, with concurrent multiplications. */
+
+static mp_limb_t
+binvert_limb_pipe_f (mp_limb_t n)
+{
+ mp_limb_t __inv = 3 * n ^ 2; /* 5 */
+ mp_limb_t __y0 = CNST_LIMB (1) - __inv * n;
+ mp_limb_t __y1 = __y0 * __y0;
+ mp_limb_t __y2 = __y1 * __y1;
+ __inv *= (1 + __y0) * (1 + __y1) * (1 + __y2);
+
+ if (GMP_NUMB_BITS > 40)
+ {
+ int __invbits = 40;
+ do {
+ __y2 *= __y2;
+ __inv *= __y2 + 1;
+ __invbits *= 2;
+ } while (__invbits < GMP_NUMB_BITS);
+ }
+
+ ASSERT ((__inv * __n & GMP_NUMB_MASK) == 1);
+ return __inv & GMP_NUMB_MASK;
+}
+#define binvert_limb_pipe(inv,n) inv = binvert_limb_pipe_f (n)
/* Like the standard version in gmp-impl.h, but with the expressions using a
"1-" form. This has the same number of steps, but "1-" is on the
@@ -175,3 +286,18 @@
{
SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_arith);
}
+double
+speed_binvert_limb_sec (struct speed_params *s)
+{
+ SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_sec);
+}
+double
+speed_binvert_limb_pipe (struct speed_params *s)
+{
+ SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_pipe);
+}
+double
+speed_binvert_limb_uintfast (struct speed_params *s)
+{
+ SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_uintfast);
+}
diff -r 1d1aff591461 -r 70fcc78764e4 tune/speed.c
--- a/tune/speed.c Thu Jul 02 07:58:25 2026 +0200
+++ b/tune/speed.c Thu Jul 02 14:13:11 2026 +0200
@@ -530,6 +530,9 @@
{ "binvert_limb_loop", speed_binvert_limb_loop, FLAG_NODATA },
{ "binvert_limb_cond", speed_binvert_limb_cond, FLAG_NODATA },
{ "binvert_limb_arith", speed_binvert_limb_arith, FLAG_NODATA },
+ { "binvert_limb_sec", speed_binvert_limb_sec, FLAG_NODATA },
+ { "binvert_limb_pipe", speed_binvert_limb_pipe, FLAG_NODATA },
+ { "binvert_limb_uintfast", speed_binvert_limb_uintfast, FLAG_NODATA },
{ "malloc_free", speed_malloc_free },
{ "malloc_realloc_free", speed_malloc_realloc_free },
diff -r 1d1aff591461 -r 70fcc78764e4 tune/speed.h
--- a/tune/speed.h Thu Jul 02 07:58:25 2026 +0200
+++ b/tune/speed.h Thu Jul 02 14:13:11 2026 +0200
@@ -153,6 +153,9 @@
double speed_binvert_limb_loop (struct speed_params *);
double speed_binvert_limb_cond (struct speed_params *);
double speed_binvert_limb_arith (struct speed_params *);
+double speed_binvert_limb_sec (struct speed_params *);
+double speed_binvert_limb_pipe (struct speed_params *);
+double speed_binvert_limb_uintfast (struct speed_params *);
double speed_mpf_init_clear (struct speed_params *);
More information about the gmp-commit
mailing list