[Gmp-commit] /var/hg/gmp: 2 new changesets

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/ac8585e811a2
changeset: 13925:ac8585e811a2
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Mon Feb 28 13:37:22 2011 +0100
description:
(mpn_rootrem_internal): Delay O(log(U)) allocations until they are known to be needed.

details:   /var/hg/gmp/rev/be51c74c1ad9
changeset: 13926:be51c74c1ad9
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Mon Feb 28 13:37:39 2011 +0100
description:
*** empty log message ***

diffstat:

 ChangeLog             |   7 +++++++
 mpn/generic/rootrem.c |  28 +++++++++++++++-------------
 2 files changed, 22 insertions(+), 13 deletions(-)

diffs (80 lines):

diff -r 87c2e4357e0e -r be51c74c1ad9 ChangeLog
--- a/ChangeLog	Sun Feb 27 23:25:20 2011 +0100
+++ b/ChangeLog	Mon Feb 28 13:37:39 2011 +0100
@@ -1,3 +1,8 @@
+2011-02-28  Torbjorn Granlund  <tege at gmplib.org>
+
+	* mpn/generic/rootrem.c (mpn_rootrem_internal): Delay O(log(U))
+	allocations until they are known to be needed.
+
 2011-02-27 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* mpn/x86/atom/sse2/mul_1.asm: New code.
@@ -252,6 +257,8 @@
 
 2011-01-31  Torbjorn Granlund  <tege at gmplib.org>
 
+	* config.guess: Recognise new Intel processors.
+
 	* config.guess: Support 'coreinhm' and 'coreisbr'.
 	* config.sub: Likewise.
 	* configure.in: Likewise.
diff -r 87c2e4357e0e -r be51c74c1ad9 mpn/generic/rootrem.c
--- a/mpn/generic/rootrem.c	Sun Feb 27 23:25:20 2011 +0100
+++ b/mpn/generic/rootrem.c	Mon Feb 28 13:37:39 2011 +0100
@@ -8,7 +8,7 @@
    ONLY SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.  IN FACT, IT'S ALMOST
    GUARANTEED THAT THEY'LL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
 
-Copyright 2002, 2005, 2009, 2010 Free Software Foundation, Inc.
+Copyright 2002, 2005, 2009, 2010, 2011 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -134,16 +134,6 @@
 
   TMP_MARK;
 
-  /* qp and wp need enough space to store S'^k where S' is an approximate
-     root. Since S' can be as large as S+2, the worst case is when S=2 and
-     S'=4. But then since we know the number of bits of S in advance, S'
-     can only be 3 at most. Similarly for S=4, then S' can be 6 at most.
-     So the worst case is S'/S=3/2, thus S'^k <= (3/2)^k * S^k. Since S^k
-     fits in un limbs, the number of extra limbs needed is bounded by
-     ceil(k*log2(3/2)/GMP_NUMB_BITS). */
-#define EXTRA 2 + (mp_size_t) (0.585 * (double) k / (double) GMP_NUMB_BITS)
-  qp = TMP_ALLOC_LIMBS (un + EXTRA); /* will contain quotient and remainder
-					of R/(k*S^(k-1)), and S^k */
   if (remp == NULL)
     {
       rp = TMP_ALLOC_LIMBS (un + 1);     /* will contain the remainder */
@@ -155,8 +145,7 @@
       rp = remp;
     }
   sp = rootp;
-  wp = TMP_ALLOC_LIMBS (un + EXTRA); /* will contain S^(k-1), k*S^(k-1),
-					and temporary for mpn_pow_1 */
+
   count_leading_zeros (cnt, up[un - 1]);
   unb = un * GMP_NUMB_BITS - cnt + GMP_NAIL_BITS;
   /* unb is the number of bits of the input U */
@@ -217,6 +206,19 @@
      Newton iteration will first compute sizes[ni-1] extra bits,
      then sizes[ni-2], ..., then sizes[0] = b. */
 
+  /* qp and wp need enough space to store S'^k where S' is an approximate
+     root. Since S' can be as large as S+2, the worst case is when S=2 and
+     S'=4. But then since we know the number of bits of S in advance, S'
+     can only be 3 at most. Similarly for S=4, then S' can be 6 at most.
+     So the worst case is S'/S=3/2, thus S'^k <= (3/2)^k * S^k. Since S^k
+     fits in un limbs, the number of extra limbs needed is bounded by
+     ceil(k*log2(3/2)/GMP_NUMB_BITS). */
+#define EXTRA 2 + (mp_size_t) (0.585 * (double) k / (double) GMP_NUMB_BITS)
+  qp = TMP_ALLOC_LIMBS (un + EXTRA); /* will contain quotient and remainder
+					of R/(k*S^(k-1)), and S^k */
+  wp = TMP_ALLOC_LIMBS (un + EXTRA); /* will contain S^(k-1), k*S^(k-1),
+					and temporary for mpn_pow_1 */
+
   wp[0] = 1; /* {sp,sn}^(k-1) = 1 */
   wn = 1;
   for (i = ni; i != 0; i--)