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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/1902efc4742e
changeset: 16918:1902efc4742e
user:      Torbjorn Granlund <torbjorng at google.com>
date:      Fri Oct 30 18:59:45 2015 +0100
description:
Add log(e) precision bits.

details:   /var/hg/gmp/rev/9290d50bb9cf
changeset: 16919:9290d50bb9cf
user:      Torbjorn Granlund <torbjorng at google.com>
date:      Fri Oct 30 19:00:28 2015 +0100
description:
ChangeLog

diffstat:

 ChangeLog    |   4 ++++
 mpf/pow_ui.c |  14 +++++++++++---
 2 files changed, 15 insertions(+), 3 deletions(-)

diffs (49 lines):

diff -r 005b53ba97a2 -r 9290d50bb9cf ChangeLog
--- a/ChangeLog	Fri Oct 30 07:59:23 2015 +0100
+++ b/ChangeLog	Fri Oct 30 19:00:28 2015 +0100
@@ -1,3 +1,7 @@
+2015-10-30  Torbjörn Granlund  <torbjorng at google.com>
+
+	* mpf/pow_ui.c: Add log(e) precision bits.
+
 2015-10-29 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* demos/factorize.c: mpz_div_2exp => mpz_tdiv_q_2exp.
diff -r 005b53ba97a2 -r 9290d50bb9cf mpf/pow_ui.c
--- a/mpf/pow_ui.c	Fri Oct 30 07:59:23 2015 +0100
+++ b/mpf/pow_ui.c	Fri Oct 30 19:00:28 2015 +0100
@@ -32,6 +32,11 @@
 #include "gmp-impl.h"
 #include "longlong.h"
 
+/* This uses a plain right-to-left square-and-multiply algorithm.
+
+   FIXME: When popcount(e) is not too small, it would probably speed things up
+   to use a k-ary sliding window algorithm.  */
+
 void
 mpf_pow_ui (mpf_ptr r, mpf_srcptr b, unsigned long int e)
 {
@@ -50,9 +55,11 @@
   count_leading_zeros (cnt, (mp_limb_t) e);
   cnt = GMP_LIMB_BITS - 1 - cnt;
 
-  /* Use a temp for all intermediate result.  We might want to add an exponent
-     derived # of bits here too, e.g.  ((cnt >> GMP_LIMB_BITS/2) != 0).  */
-  mpf_init2 (t, mpf_get_prec (r) + GMP_LIMB_BITS);
+  /* Increase computation precision as a function of the exponent.  Adding
+     log2(popcount(e) + log2(e)) bits should be sufficient, but we add log2(e),
+     i.e. much more.  With mpf's rounding of precision to whole limbs, this
+     will be excessive only when limbs are artificially small.  */
+  mpf_init2 (t, mpf_get_prec (r) + cnt);
 
   mpf_set (t, b);		/* consume most significant bit */
   while (--cnt > 0)
@@ -62,6 +69,7 @@
 	mpf_mul (t, t, b);
     }
 
+  /* Do the last iteration specially in order to save a copy operation.  */
   if (e & 1)
     {
       mpf_mul (t, t, t);