[Gmp-commit] /home/hgfiles/gmp: 3 new changesets

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/83c018467c8d
changeset: 13041:83c018467c8d
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sat Dec 12 00:12:10 2009 +0100
description:
Remove an unused variable.

details:   /home/hgfiles/gmp/rev/46b2412f4210
changeset: 13042:46b2412f4210
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sat Dec 12 12:52:17 2009 +0100
description:
Trivial Merge.

details:   /home/hgfiles/gmp/rev/26537180dd3b
changeset: 13043:26537180dd3b
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sat Dec 12 12:54:36 2009 +0100
description:
(mpn_mu_bdiv_qr_itch): Rewrite.

diffstat:

 ChangeLog                 |   4 ++++
 mpn/generic/binvert.c     |   2 +-
 mpn/generic/mu_bdiv_qr.c  |  25 +++++++++++++++++++++----
 tests/mpn/t-mulmod_bnm1.c |   6 ++++--
 4 files changed, 30 insertions(+), 7 deletions(-)

diffs (87 lines):

diff -r 8155c651b234 -r 26537180dd3b ChangeLog
--- a/ChangeLog	Sat Dec 12 00:05:18 2009 +0100
+++ b/ChangeLog	Sat Dec 12 12:54:36 2009 +0100
@@ -1,3 +1,7 @@
+2009-12-12  Torbjorn Granlund  <tege at gmplib.org>
+
+	* mpn/generic/mu_bdiv_qr.c (mpn_mu_bdiv_qr_itch): Rewrite.
+
 2009-12-11  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/generic/binvert.c: Use mpn_mulmod_bnm1 instead of FFT wrapping.
diff -r 8155c651b234 -r 26537180dd3b mpn/generic/binvert.c
--- a/mpn/generic/binvert.c	Sat Dec 12 00:05:18 2009 +0100
+++ b/mpn/generic/binvert.c	Sat Dec 12 12:54:36 2009 +0100
@@ -62,7 +62,7 @@
 void
 mpn_binvert (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_ptr scratch)
 {
-  mp_ptr xp, tp;
+  mp_ptr xp;
   mp_size_t rn, newrn;
   mp_size_t sizes[NPOWS], *sizp;
   mp_limb_t di;
diff -r 8155c651b234 -r 26537180dd3b mpn/generic/mu_bdiv_qr.c
--- a/mpn/generic/mu_bdiv_qr.c	Sat Dec 12 00:05:18 2009 +0100
+++ b/mpn/generic/mu_bdiv_qr.c	Sat Dec 12 12:54:36 2009 +0100
@@ -213,6 +213,8 @@
 
       mpn_mullo_n (qp, np, ip, in);		/* low `in' quotient limbs */
 #if WANT_FFT
+      /* FIXME: We might perform extremely unbalanced multiplies here, were FFT
+	 is not efficient.  */
       if (ABOVE_THRESHOLD (dn, MUL_FFT_MODF_THRESHOLD))
 	{
 	  k = mpn_fft_best_k (dn, 0);
@@ -267,16 +269,31 @@
 mp_size_t
 mpn_mu_bdiv_qr_itch (mp_size_t nn, mp_size_t dn)
 {
-  mp_size_t qn;
+  mp_size_t qn, in, m, itch_invert, itch;
+  mp_size_t b;
 
-  qn = nn;
+  qn = nn - dn;
 
   if (qn > dn)
     {
-      return 4 * dn;		/* FIXME FIXME FIXME need mpn_fft_next_size */
+      b = (qn - 1) / dn + 1;	/* ceil(qn/dn), number of blocks */
+      in = (qn - 1) / b + 1;	/* ceil(qn/b) = ceil(qn / ceil(qn/dn)) */
+      return in + mpn_binvert_itch (in);
     }
   else
     {
-      return 2 * qn + 1 + 2;	/* FIXME FIXME FIXME need mpn_fft_next_size */
+      in = qn - (qn >> 1);
+#if WANT_FFT
+      if (ABOVE_THRESHOLD (dn, MUL_FFT_MODF_THRESHOLD))
+	{
+	  m = mpn_fft_next_size (dn, mpn_fft_best_k (dn, 0));
+	  m = MAX (dn + in, m);
+	}
+      else
+#endif
+	m = dn + in;
+      itch_invert = mpn_binvert_itch (in);
+      itch = MAX (itch_invert, m);
+      return in + itch;
     }
 }
diff -r 8155c651b234 -r 26537180dd3b tests/mpn/t-mulmod_bnm1.c
--- a/tests/mpn/t-mulmod_bnm1.c	Sat Dec 12 00:05:18 2009 +0100
+++ b/tests/mpn/t-mulmod_bnm1.c	Sat Dec 12 12:54:36 2009 +0100
@@ -151,8 +151,10 @@
       mpn_random2 (ap, an);
       mpn_random2 (bp, bn);
 
-      /* Sometime trigger the an = -1 or bn = -1 or an*bn == -1 Mod(B^{n/2}+1) */
-      if ((test & 0x1f) == 1 && n > 1) {
+      /* Sometime trigger the borderline conditions
+	 A = -1,0,+1 or B = -1,0,+1 or A*B == -1,0,1 Mod(B^{n/2}+1).
+	 This only makes sense if there is at least a split, i.e. n is even. */
+      if ((test & 0x1f) == 1 && (n & 1) == 0) {
 	mp_size_t x;
 	MPN_COPY (ap, ap + (n >> 1), an - (n >> 1));
 	MPN_ZERO (ap + an - (n >> 1) , n - an);