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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/9ead2f83bc43
changeset: 14217:9ead2f83bc43
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Fri Jul 15 22:32:54 2011 +0200
description:
Swap around some registers to silence 'as' warnings.

details:   /var/hg/gmp/rev/12e8d749f39d
changeset: 14218:12e8d749f39d
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Fri Jul 15 22:33:02 2011 +0200
description:
*** empty log message ***

details:   /var/hg/gmp/rev/c792aed068d3
changeset: 14219:c792aed068d3
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Wed Aug 03 22:06:17 2011 +0200
description:
Trivial merge.

diffstat:

 ChangeLog               |  13 ++++++++
 dumbmp.c                |  78 +++++++++++++++++++++++++++++++++++++++++++++---
 mpn/arm/invert_limb.asm |  26 ++++++++--------
 3 files changed, 99 insertions(+), 18 deletions(-)

diffs (175 lines):

diff -r 17adfcccc3db -r c792aed068d3 ChangeLog
--- a/ChangeLog	Thu Jul 14 15:25:59 2011 +0200
+++ b/ChangeLog	Wed Aug 03 22:06:17 2011 +0200
@@ -1,3 +1,16 @@
+2011-08-03  Torbjorn Granlund  <tege at gmplib.org>
+
+	* dumbmp.c (mpz_tdiv_qr): Correctly handle dividend value being equal
+	to divisor value.
+	(mpz_root): Create reasonable starting approximation.
+	(mpz_sqrt): New function.
+	(mpz_mul_2exp): Add faster block shifting code, disabled for now.
+
+2011-07-15  Torbjorn Granlund  <tege at gmplib.org>
+
+	* mpn/arm/invert_limb.asm: Swap around some registers to silence 'as'
+	warnings.
+
 2011-07-14  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/generic/dcpi1_bdiv_q.c (mpn_dcpi1_bdiv_q): Get mpn_sub_1 size
diff -r 17adfcccc3db -r c792aed068d3 dumbmp.c
--- a/dumbmp.c	Thu Jul 14 15:25:59 2011 +0200
+++ b/dumbmp.c	Wed Aug 03 22:06:17 2011 +0200
@@ -517,6 +517,34 @@
 mpz_mul_2exp (mpz_t r, mpz_t a, unsigned long int bcnt)
 {
   mpz_set (r, a);
+
+#if 0
+  {
+    unsigned long int lcnt;
+
+    lcnt = bcnt / GMP_LIMB_BITS;
+    if (lcnt > 0)
+      {
+	int rn = ABSIZ (r);
+	mp_limb_t *rp;
+	int i;
+
+	mpz_realloc (r, rn + lcnt);
+	rp = PTR (r);
+
+	for (i = rn - 1; i >= 0; i--)
+	  rp[i + lcnt] = rp[i];
+	for (i = lcnt - 1; i >= 0; i--)
+	  rp[i] = 0;
+
+	rn += lcnt;
+	SIZ (r) = SIZ (r) >= 0 ? rn : -rn;
+
+	bcnt %= GMP_LIMB_BITS;
+      }
+  }
+#endif
+
   while (bcnt)
     {
       mpz_add (r, r, r);
@@ -658,7 +686,7 @@
   mpz_init_set (tmpb, b);
   mpz_set_ui (q, 0L);
 
-  if (mpz_cmp (tmpr, tmpb) > 0)
+  if (mpz_cmp (tmpr, tmpb) >= 0)
     {
       cnt = mpz_sizeinbase (tmpr, 2) - mpz_sizeinbase (tmpb, 2) + 1;
       mpz_mul_2exp (tmpb, tmpb, cnt);
@@ -900,9 +928,12 @@
       mpz_set (x, y);
       return;
     }
-  mpz_init (t);
-  mpz_init_set (u, y);
-  do
+
+  /* One-bit initial approximation */
+  mpz_init_set_ui (u, 1);
+  mpz_mul_2exp (u, u, ((mpz_sizeinbase (y, 2) - 1) / z) + 1);
+
+  for (;;)
     {
       mpz_pow_ui (t, u, z - 1);
       mpz_tdiv_q (t, y, t);
@@ -912,8 +943,45 @@
 	break;
       mpz_set (u, t);
     }
-  while (1);
+
   mpz_set (x, u);
   mpz_clear (t);
   mpz_clear (u);
 }
+
+/* x=floor(y^(1/2)) */
+void
+mpz_sqrt (mpz_t x, mpz_t y)
+{
+  mpz_t t, u;
+
+  if (mpz_sgn (y) < 0)
+    {
+      fprintf (stderr, "mpz_sqrt does not accept negative values\n");
+      abort ();
+    }
+  if (mpz_cmp_ui (y, 1) <= 0)
+    {
+      mpz_set (x, y);
+      return;
+    }
+  mpz_init (t);
+
+  /* One-bit initial approximation */
+  mpz_init_set_ui (u, 1);
+  mpz_mul_2exp (u, u, ((mpz_sizeinbase (y, 2) - 1) / 2) + 1);
+
+  for (;;)
+    {
+      mpz_tdiv_q (t, y, u);
+      mpz_add (t, t, u);
+      mpz_tdiv_q_2exp (t, t, 1);
+      if (mpz_cmp (t, u) >= 0)
+	break;
+      mpz_set (u, t);
+    }
+
+  mpz_set (x, u);
+  mpz_clear (t);
+  mpz_clear (u);
+}
diff -r 17adfcccc3db -r c792aed068d3 mpn/arm/invert_limb.asm
--- a/mpn/arm/invert_limb.asm	Thu Jul 14 15:25:59 2011 +0200
+++ b/mpn/arm/invert_limb.asm	Wed Aug 03 22:06:17 2011 +0200
@@ -1,6 +1,6 @@
 dnl  ARM mpn_invert_limb -- Invert a normalized limb.
 
-dnl  Copyright 2001, 2009 Free Software Foundation, Inc.
+dnl  Copyright 2001, 2009, 2011 Free Software Foundation, Inc.
 
 dnl  This file is part of the GNU MP Library.
 
@@ -27,21 +27,21 @@
 	mov	r3, r3, asl #1
 	ldrh	r3, [r3, r2]
 	mov	r1, r3, asl #17
-	mul	r3, r3, r3
-	umull	r12, r2, r3, r0
+	mul	r12, r3, r3
+	umull	r3, r2, r12, r0
 	sub	r1, r1, r2, asl #1
-	umull	r12, r2, r1, r1
-	umull	r3, r12, r0, r12
-	umull	r2, r3, r0, r2
-	adds	r2, r2, r12
-	adc	r3, r3, #0
-	rsb	r1, r3, r1
+	umull	r3, r2, r1, r1
+	umull	r12, r3, r0, r3
+	umull	r2, r12, r0, r2
+	adds	r2, r2, r3
+	adc	r12, r12, #0
+	rsb	r1, r12, r1
 	mvn	r2, r2, lsr #30
 	add	r2, r2, r1, asl #2
-	umull	r3, r12, r0, r2
-	adds	r1, r3, r0
-	adc	r12, r12, r0
-	rsb	r0, r12, r2
+	umull	r12, r3, r0, r2
+	adds	r1, r12, r0
+	adc	r3, r3, r0
+	rsb	r0, r3, r2
 	bx	lr
 
 	ALIGN(4)