[Gmp-commit] /home/hgfiles/gmp: (mpn_mul_fft_full): Handle carry-out from 2nd...

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/e06c4e48a9c6
changeset: 13057:e06c4e48a9c6
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sun Dec 13 17:55:41 2009 +0100
description:
(mpn_mul_fft_full): Handle carry-out from 2nd mpn_mul_fft.

diffstat:

 ChangeLog             |   4 ++++
 mpn/generic/mul_fft.c |  13 ++++++++-----
 2 files changed, 12 insertions(+), 5 deletions(-)

diffs (42 lines):

diff -r 20c811bc3f8f -r e06c4e48a9c6 ChangeLog
--- a/ChangeLog	Sun Dec 13 16:50:36 2009 +0100
+++ b/ChangeLog	Sun Dec 13 17:55:41 2009 +0100
@@ -1,5 +1,9 @@
 2009-12-13  Torbjorn Granlund  <tege at gmplib.org>
 
+	* mpn/generic/mul_fft.c (mpn_mul_fft_full): Handle carry-out from 2nd
+	mpn_mul_fft, add an ASSERT for the 1sd mpn_mul_fft.  Replace some
+	comments on cc's range with ASSERTs.
+
 	* mpn/generic/gcdext.c (compute_v): Normalize tp[] after mpn_mul.
 
 	* mpz/powm.c: Rework buffer handling.
diff -r 20c811bc3f8f -r e06c4e48a9c6 mpn/generic/mul_fft.c
--- a/mpn/generic/mul_fft.c	Sun Dec 13 16:50:36 2009 +0100
+++ b/mpn/generic/mul_fft.c	Sun Dec 13 17:55:41 2009 +0100
@@ -973,17 +973,20 @@
 		 nl, ml, pl2, pl3, k2));
 
   ASSERT_ALWAYS(pl3 <= pl);
-  mpn_mul_fft (op, pl3, n, nl, m, ml, k3);     /* mu */
+  cc = mpn_mul_fft (op, pl3, n, nl, m, ml, k3);     /* mu */
+  ASSERT(cc == 0);
   pad_op = __GMP_ALLOCATE_FUNC_LIMBS (pl2);
-  mpn_mul_fft (pad_op, pl2, n, nl, m, ml, k2); /* lambda */
-  cc = mpn_sub_n (pad_op, pad_op, op, pl2);    /* lambda - low(mu) */
+  cc = mpn_mul_fft (pad_op, pl2, n, nl, m, ml, k2); /* lambda */
+  cc = -cc + mpn_sub_n (pad_op, pad_op, op, pl2);    /* lambda - low(mu) */
   /* 0 <= cc <= 1 */
+  ASSERT(0 <= cc && cc <= 1);
   l = pl3 - pl2; /* l = pl2 / 2 since pl3 = 3/2 * pl2 */
   c2 = mpn_add_n (pad_op, pad_op, op + pl2, l);
-  cc = mpn_add_1 (pad_op + l, pad_op + l, l, (mp_limb_t) c2) - cc; /* -1 <= cc <= 1 */
+  cc = mpn_add_1 (pad_op + l, pad_op + l, l, (mp_limb_t) c2) - cc;
+  ASSERT(-1 <= cc && cc <= 1);
   if (cc < 0)
     cc = mpn_add_1 (pad_op, pad_op, pl2, (mp_limb_t) -cc);
-  /* 0 <= cc <= 1 */
+  ASSERT(0 <= cc && cc <= 1);
   /* now lambda-mu = {pad_op, pl2} - cc mod 2^(pl2*GMP_NUMB_BITS)+1 */
   oldcc = cc;
 #if HAVE_NATIVE_mpn_add_n_sub_n