[Gmp-commit] /var/hg/gmp: 10 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Wed Nov 7 20:31:57 UTC 2018
details: /var/hg/gmp/rev/6a885b3a2125
changeset: 17666:6a885b3a2125
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Tue Oct 30 23:22:21 2018 +0100
description:
tests/mpz/t-nextprime.c: Add one more interval
details: /var/hg/gmp/rev/81976c309e55
changeset: 17667:81976c309e55
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Wed Oct 31 18:27:54 2018 +0100
description:
mpn/generic/fib2m.c: New file, Fibonacci numbers modulo ...
details: /var/hg/gmp/rev/3ee1d7b07575
changeset: 17668:3ee1d7b07575
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Wed Oct 31 18:31:40 2018 +0100
description:
configure.ac (gmp_mpn_functions): Add fib2m.
gmp-impl.h: Declare mpn_fib2m.
details: /var/hg/gmp/rev/36b5f67a1c1a
changeset: 17669:36b5f67a1c1a
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Wed Oct 31 18:33:47 2018 +0100
description:
tests/mpn/t-fib2m.c: New file, test for mpn_fib2m
details: /var/hg/gmp/rev/446a4cd53c41
changeset: 17670:446a4cd53c41
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Wed Oct 31 18:36:05 2018 +0100
description:
tests/mpn/Makefile.am (check_PROGRAMS): Add t-fib2m
details: /var/hg/gmp/rev/742577b43762
changeset: 17671:742577b43762
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Wed Oct 31 18:39:57 2018 +0100
description:
tests/mpz/t-pprime_p.c (check_fermat_mersenne): New set of tests.
details: /var/hg/gmp/rev/3577166c8e1e
changeset: 17672:3577166c8e1e
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Wed Oct 31 18:40:38 2018 +0100
description:
mpn/generic/mod_1_3.c: typo in a comment
details: /var/hg/gmp/rev/5a32958fc655
changeset: 17673:5a32958fc655
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Wed Oct 31 18:41:15 2018 +0100
description:
mpz/nextprime.c: Use tdiv instead of fdiv
details: /var/hg/gmp/rev/363c8b34c452
changeset: 17674:363c8b34c452
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Nov 01 19:56:03 2018 +0100
description:
tests/mpn/t-fib2m.c: Avoid mis-triggering errors when the modulus is even
details: /var/hg/gmp/rev/800e0c75fe00
changeset: 17675:800e0c75fe00
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Nov 07 21:24:41 2018 +0100
description:
ChangeLog
diffstat:
ChangeLog | 22 +++
configure.ac | 2 +-
gmp-impl.h | 3 +
mpn/generic/fib2m.c | 245 ++++++++++++++++++++++++++++++++++
mpn/generic/mod_1_3.c | 2 +-
mpz/nextprime.c | 2 +-
tests/mpn/Makefile.am | 4 +-
tests/mpn/t-fib2m.c | 344 ++++++++++++++++++++++++++++++++++++++++++++++++
tests/mpz/t-nextprime.c | 17 +-
tests/mpz/t-pprime_p.c | 49 ++++++-
10 files changed, 678 insertions(+), 12 deletions(-)
diffs (truncated from 847 to 300 lines):
diff -r 78b9d443b0e9 -r 800e0c75fe00 ChangeLog
--- a/ChangeLog Wed Nov 07 09:52:36 2018 +0100
+++ b/ChangeLog Wed Nov 07 21:24:41 2018 +0100
@@ -1,3 +1,16 @@
+2018-11-07 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpz/lucnum2_ui.c: Use mpn_rsblsh1_n if available.
+ * tests/mpz/t-nextprime.c: Add one more interval.
+ * tests/mpz/t-pprime_p.c (check_fermat_mersenne): New tests.
+ * mpn/generic/mod_1_3.c: typo in a comment.
+
+ * mpn/generic/fib2m.c: New file, Fibonacci numbers modulo.
+ * configure.ac (gmp_mpn_functions): Add it.
+ * gmp-impl.h: Declare mpn_fib2m.
+ * tests/mpn/t-fib2m.c: New file, tests for mpn_fib2m.
+ * tests/mpn/Makefile.am (check_PROGRAMS): Add t-fib2m.
+
2018-11-07 Torbjörn Granlund <tg at gmplib.org>
* configure.ac (arm): Support a12 and a17.
@@ -14,6 +27,15 @@
* mpn/arm/v7a/cora17/addmul_1.asm: Likewise.
* mpn/arm/v7a/cora17/submul_1.asm: Likewise.
+2018-10-18 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpn/generic/fib2_ui.c: Simplify the possible -2 case.
+
+2018-07-19 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpz/millerrabin.c (mod_eq_m1): New function, equality with -1.
+ * mpz/powm_ui.c: Small optimisations.
+
2018-07-03 Torbjörn Granlund <tg at gmplib.org>
* mpn/x86_64/lshift.asm: Remove cnt = 1 special code.
diff -r 78b9d443b0e9 -r 800e0c75fe00 configure.ac
--- a/configure.ac Wed Nov 07 09:52:36 2018 +0100
+++ b/configure.ac Wed Nov 07 21:24:41 2018 +0100
@@ -2946,7 +2946,7 @@
mul_1 addmul_1 submul_1 \
add_err1_n add_err2_n add_err3_n sub_err1_n sub_err2_n sub_err3_n \
lshift rshift dive_1 diveby3 divis divrem divrem_1 divrem_2 \
- fib2_ui mod_1 mod_34lsub1 mode1o pre_divrem_1 pre_mod_1 dump \
+ fib2_ui fib2m mod_1 mod_34lsub1 mode1o pre_divrem_1 pre_mod_1 dump \
mod_1_1 mod_1_2 mod_1_3 mod_1_4 lshiftc \
mul mul_fft mul_n sqr mul_basecase sqr_basecase nussbaumer_mul \
mulmid_basecase toom42_mulmid mulmid_n mulmid \
diff -r 78b9d443b0e9 -r 800e0c75fe00 gmp-impl.h
--- a/gmp-impl.h Wed Nov 07 09:52:36 2018 +0100
+++ b/gmp-impl.h Wed Nov 07 21:24:41 2018 +0100
@@ -1133,6 +1133,9 @@
#define mpn_fib2_ui __MPN(fib2_ui)
__GMP_DECLSPEC mp_size_t mpn_fib2_ui (mp_ptr, mp_ptr, unsigned long);
+#define mpn_fib2m __MPN(fib2m)
+__GMP_DECLSPEC int mpn_fib2m (mp_ptr, mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t);
+
/* Remap names of internal mpn functions. */
#define __clz_tab __MPN(clz_tab)
#define mpn_udiv_w_sdiv __MPN(udiv_w_sdiv)
diff -r 78b9d443b0e9 -r 800e0c75fe00 mpn/generic/fib2m.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/fib2m.c Wed Nov 07 21:24:41 2018 +0100
@@ -0,0 +1,245 @@
+/* mpn_fib2m -- calculate Fibonacci numbers, modulo m.
+
+ THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST
+ CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN
+ FUTURE GNU MP RELEASES.
+
+Copyright 2001, 2002, 2005, 2009, 2018 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 <stdio.h>
+#include "gmp-impl.h"
+#include "longlong.h"
+
+
+/* Stores |{ap,n}-{bp,n}| in {rp,n},
+ returns the sign of {ap,n}-{bp,n}. */
+static int
+abs_sub_n (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
+{
+ mp_limb_t x, y;
+ while (--n >= 0)
+ {
+ x = ap[n];
+ y = bp[n];
+ if (x != y)
+ {
+ ++n;
+ if (x > y)
+ {
+ mpn_sub_n (rp, ap, bp, n);
+ return 1;
+ }
+ else
+ {
+ mpn_sub_n (rp, bp, ap, n);
+ return -1;
+ }
+ }
+ rp[n] = 0;
+ }
+ return 0;
+}
+
+/* Store F[n] at fp and F[n-1] at f1p. Both are computed modulo m.
+ fp and f1p should have room for mn*2+1 limbs.
+
+ The sign of one or both the values may be flipped (n-F, instead of F),
+ the return value is 0 (zero) if the signs are coherent (both positive
+ or both negative) and 1 (one) otherwise.
+
+ Notes:
+
+ In F[2k+1] with k even, +2 is applied to 4*F[k]^2 just by ORing into the
+ low limb.
+
+ In F[2k+1] with k odd, -2 is applied to F[k-1]^2 just by ORing into the
+ low limb.
+
+ Should {tp, 2 * mn} be passed as a scratch pointer?
+ Should the call to mpn_fib2_ui() obtain (up to) 2*mn limbs?
+*/
+
+int
+mpn_fib2m (mp_ptr fp, mp_ptr f1p, mp_srcptr np, mp_size_t nn, mp_srcptr mp, mp_size_t mn)
+{
+ unsigned long nfirst;
+ mp_limb_t nh;
+ mp_bitcnt_t mbi, nbi;
+ mp_size_t sn, fn;
+ int fcnt, ncnt;
+ unsigned pb;
+
+ ASSERT (! MPN_OVERLAP_P (fp, MAX(2*mn+1,5), f1p, MAX(2*mn+1,5)));
+ ASSERT (nn > 0 && np[nn - 1] != 0);
+
+#if GMP_NUMB_BITS % 16 == 0
+ if (UNLIKELY (ULONG_MAX / (23 * (GMP_NUMB_BITS / 16)) <= mn))
+ nfirst = ULONG_MAX;
+ else
+ nfirst = mn * (23 * (GMP_NUMB_BITS / 16));
+#else
+ mbi = (mp_bitcnt_t) mn * GMP_NUMB_BITS;
+
+ if (UNLIKELY (ULONG_MAX / 23 < mbi))
+ {
+ if (UNLIKELY (ULONG_MAX / 23 * 16 <= mbi))
+ nfirst = ULONG_MAX;
+ else
+ nfirst = mbi / 16 * 23;
+ }
+ else
+ nfirst = mbi * 23 / 16;
+#endif
+ sn = nn - 1;
+ nh = np[sn];
+ count_leading_zeros (ncnt, nh);
+ count_leading_zeros (fcnt, nfirst);
+
+ if (fcnt >= ncnt)
+ {
+ ncnt = fcnt - ncnt;
+ nh >>= ncnt;
+ }
+ else if (sn > 0)
+ {
+ ncnt -= fcnt;
+ nh <<= ncnt;
+ ncnt = GMP_NUMB_BITS - ncnt;
+ --sn;
+ nh |= np[sn] >> ncnt;
+ }
+ else
+ ncnt = 0;
+
+ nbi = sn * GMP_NUMB_BITS + ncnt;
+ if (nh > nfirst)
+ {
+ nh >>= 1;
+ ++nbi;
+ }
+
+ ASSERT (nh <= nfirst);
+ /* Take a starting pair from mpn_fib2_ui. */
+ fn = mpn_fib2_ui (fp, f1p, nh);
+ MPN_ZERO (fp + fn, mn - fn);
+ MPN_ZERO (f1p + fn, mn - fn);
+
+ if (nbi == 0)
+ {
+ if (fn == mn)
+ {
+ mp_limb_t qp[2];
+ mpn_tdiv_qr (qp, fp, 0, fp, fn, mp, mn);
+ mpn_tdiv_qr (qp, f1p, 0, f1p, fn, mp, mn);
+ }
+
+ return 0;
+ }
+ else
+ {
+ mp_ptr xp, yp, zp, tp;
+ unsigned pb = nh & 1;
+ int neg;
+ TMP_DECL;
+
+ TMP_MARK;
+
+ tp = TMP_ALLOC_LIMBS (2 * mn + (mn < 2));
+
+ do
+ {
+ mp_ptr rp;
+ /* Here fp==F[k] and f1p==F[k-1], with k being the bits of n from
+ nbi upwards.
+
+ Based on the next bit of n, we'll double to the pair
+ fp==F[2k],f1p==F[2k-1] or fp==F[2k+1],f1p==F[2k], according as
+ that bit is 0 or 1 respectively. */
+
+ mpn_sqr (tp, fp, mn);
+ mpn_sqr (fp, f1p, mn);
+
+ /* Calculate F[2k-1] = F[k]^2 + F[k-1]^2. */
+ f1p[2 * mn] = mpn_add_n (f1p, tp, fp, 2 * mn);
+
+ /* Calculate F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k.
+ pb is the low bit of our implied k. */
+
+ /* fp is F[k-1]^2 == 0 or 1 mod 4, like all squares. */
+ ASSERT ((fp[0] & 2) == 0);
+ ASSERT (pb == (pb & 1));
+ ASSERT ((fp[0] + (pb ? 2 : 0)) == (fp[0] | (pb << 1)));
+ fp[0] |= pb << 1; /* possible -2 */
+#if HAVE_NATIVE_mpn_rsblsh2_n
+ fp[2 * mn] = 1 + mpn_rsblsh2_n (fp, fp, tp, 2 * mn);
+ MPN_INCR_U(fp, 2 * mn + 1, (1 ^ pb) << 1); /* possible +2 */
+ fp[2 * mn] = (fp[2 * mn] - 1) & GMP_NUMB_MAX;
+#else
+ {
+ mp_limb_t c;
+
+ c = mpn_lshift (tp, tp, 2 * mn, 2);
+ tp[0] |= (1 ^ pb) << 1; /* possible +2 */
+ c -= mpn_sub_n (fp, tp, fp, 2 * mn);
+ fp[2 * mn] = c & GMP_NUMB_MAX;
+ }
+#endif
+ neg = fp[2 * mn] == GMP_NUMB_MAX;
+
+ /* Calculate F[2k-1] = F[k]^2 + F[k-1]^2 */
+ /* Calculate F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k */
+
+ /* Calculate F[2k] = F[2k+1] - F[2k-1], replacing the unwanted one of
+ F[2k+1] and F[2k-1]. */
+ --nbi;
+ pb = (np [nbi / GMP_NUMB_BITS] >> (nbi % GMP_NUMB_BITS)) & 1;
+ rp = pb ? f1p : fp;
+ if (neg)
+ {
+ /* Calculate -(F[2k+1] - F[2k-1]) */
+ rp[2 * mn] = f1p[2 * mn] + 1 - mpn_sub_n (rp, f1p, fp, 2 * mn);
+ neg = ! pb;
+ if (pb) /* fp not overwritten, negate it. */
+ fp [2 * mn] = 1 ^ mpn_neg (fp, fp, 2 * mn);
+ }
+ else
+ {
+ neg = abs_sub_n (rp, fp, f1p, 2 * mn + 1) < 0;
+ }
+
More information about the gmp-commit
mailing list