diff options
author | vlefevre <vlefevre@280ebfd0-de03-0410-8827-d642c229c3f4> | 2010-08-17 09:10:13 +0000 |
---|---|---|
committer | vlefevre <vlefevre@280ebfd0-de03-0410-8827-d642c229c3f4> | 2010-08-17 09:10:13 +0000 |
commit | c9583bdfe064e1069828e518533f7bc29a8fdddb (patch) | |
tree | 2400842d4095628b8486fbeabaf7bc7b8af4ed02 /src/mpn_exp.c | |
parent | 50ac5b5985174201c7fa6e20496cd2b096107001 (diff) | |
download | mpfr-c9583bdfe064e1069828e518533f7bc29a8fdddb.tar.gz |
Source reorganization. In short:
* Added directories and moved related files into them:
- src for the MPFR source files (to build the library).
- doc for documentation files (except INSTALL, README...).
- tools for various tools (scripts) and mbench.
- tune for tuneup-related source files.
- other for other source files (not distributed in tarballs).
Existing directories:
- tests for the source files of the test suite (make check).
- examples for examples.
- m4 for m4 files.
* Renamed configure.in to configure.ac.
* Added/updated Makefile.am files where needed.
* Updated acinclude.m4 and configure.ac (AC_CONFIG_FILES line).
* Updated the documentation (INSTALL, README, doc/README.dev and
doc/mpfr.texi).
* Updated NEWS and TODO.
* Updated the scripts now in tools.
The following script was used:
#!/usr/bin/env zsh
svn mkdir doc other src tools tune
svn mv ${${(M)$(sed -n '/libmpfr_la_SOURCES/,/[^\]$/p' \
Makefile.am):#*.[ch]}:#get_patches.c} mparam_h.in \
round_raw_generic.c jyn_asympt.c src
svn mv mbench check_inits_clears coverage get_patches.sh mpfrlint \
nightly-test update-patchv update-version tools
svn mv bidimensional_sample.c speed.c tuneup.c tune
svn mv *.{c,h} other
svn mv FAQ.html README.dev algorithm* faq.xsl fdl.texi mpfr.texi \
update-faq doc
svn mv configure.in configure.ac
svn cp Makefile.am src/Makefile.am
svn rm replace_all
[Modifying some files, see above]
svn add doc/Makefile.am
svn add tune/Makefile.am
git-svn-id: svn://scm.gforge.inria.fr/svn/mpfr/trunk@7087 280ebfd0-de03-0410-8827-d642c229c3f4
Diffstat (limited to 'src/mpn_exp.c')
-rw-r--r-- | src/mpn_exp.c | 175 |
1 files changed, 175 insertions, 0 deletions
diff --git a/src/mpn_exp.c b/src/mpn_exp.c new file mode 100644 index 000000000..ea2921feb --- /dev/null +++ b/src/mpn_exp.c @@ -0,0 +1,175 @@ +/* mpfr_mpn_exp -- auxiliary function for mpfr_get_str and mpfr_set_str + +Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. +Contributed by the Arenaire and Caramel projects, INRIA. +Contributed by Alain Delplanque and Paul Zimmermann. + +This file is part of the GNU MPFR Library. + +The GNU MPFR Library is free software; you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 3 of the License, or (at your +option) any later version. + +The GNU MPFR Library is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public +License for more details. + +You should have received a copy of the GNU Lesser General Public License +along with the GNU MPFR Library; see the file COPYING.LESSER. If not, see +http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc., +51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */ + + +#define MPFR_NEED_LONGLONG_H +#include "mpfr-impl.h" + +/* this function computes an approximation of b^e in {a, n}, with exponent + stored in exp_r. The computed value is rounded toward zero (truncated). + It returns an integer f such that the final error is bounded by 2^f ulps, + that is: + a*2^exp_r <= b^e <= 2^exp_r (a + 2^f), + where a represents {a, n}, i.e. the integer + a[0] + a[1]*B + ... + a[n-1]*B^(n-1) where B=2^GMP_NUMB_BITS + + Return -1 is the result is exact. + Return -2 if an overflow occurred in the computation of exp_r. +*/ + +long +mpfr_mpn_exp (mp_limb_t *a, mpfr_exp_t *exp_r, int b, mpfr_exp_t e, size_t n) +{ + mp_limb_t *c, B; + mpfr_exp_t f, h; + int i; + unsigned long t; /* number of bits in e */ + unsigned long bits; + size_t n1; + unsigned int error; /* (number - 1) of loop a^2b inexact */ + /* error == t means no error */ + int err_s_a2 = 0; + int err_s_ab = 0; /* number of error when shift A^2, AB */ + MPFR_TMP_DECL(marker); + + MPFR_ASSERTN(e > 0); + MPFR_ASSERTN((2 <= b) && (b <= 62)); + + MPFR_TMP_MARK(marker); + + /* initialization of a, b, f, h */ + + /* normalize the base */ + B = (mp_limb_t) b; + count_leading_zeros (h, B); + + bits = GMP_NUMB_BITS - h; + + B = B << h; + h = - h; + + /* allocate space for A and set it to B */ + c = (mp_limb_t*) MPFR_TMP_ALLOC(2 * n * BYTES_PER_MP_LIMB); + a [n - 1] = B; + MPN_ZERO (a, n - 1); + /* initial exponent for A: invariant is A = {a, n} * 2^f */ + f = h - (n - 1) * GMP_NUMB_BITS; + + /* determine number of bits in e */ + count_leading_zeros (t, (mp_limb_t) e); + + t = GMP_NUMB_BITS - t; /* number of bits of exponent e */ + + error = t; /* error <= GMP_NUMB_BITS */ + + MPN_ZERO (c, 2 * n); + + for (i = t - 2; i >= 0; i--) + { + + /* determine precision needed */ + bits = n * GMP_NUMB_BITS - mpn_scan1 (a, 0); + n1 = (n * GMP_NUMB_BITS - bits) / GMP_NUMB_BITS; + + /* square of A : {c+2n1, 2(n-n1)} = {a+n1, n-n1}^2 */ + mpn_sqr_n (c + 2 * n1, a + n1, n - n1); + + /* set {c+n, 2n1-n} to 0 : {c, n} = {a, n}^2*K^n */ + + /* check overflow on f */ + if (MPFR_UNLIKELY(f < MPFR_EXP_MIN/2 || f > MPFR_EXP_MAX/2)) + { + overflow: + MPFR_TMP_FREE(marker); + return -2; + } + /* FIXME: Could f = 2*f + n * GMP_NUMB_BITS be used? */ + f = 2*f; + MPFR_SADD_OVERFLOW (f, f, n * GMP_NUMB_BITS, + mpfr_exp_t, mpfr_uexp_t, + MPFR_EXP_MIN, MPFR_EXP_MAX, + goto overflow, goto overflow); + if ((c[2*n - 1] & MPFR_LIMB_HIGHBIT) == 0) + { + /* shift A by one bit to the left */ + mpn_lshift (a, c + n, n, 1); + a[0] |= mpn_lshift (c + n - 1, c + n - 1, 1, 1); + f --; + if (error != t) + err_s_a2 ++; + } + else + MPN_COPY (a, c + n, n); + + if ((error == t) && (2 * n1 <= n) && + (mpn_scan1 (c + 2 * n1, 0) < (n - 2 * n1) * GMP_NUMB_BITS)) + error = i; + + if (e & ((mpfr_exp_t) 1 << i)) + { + /* multiply A by B */ + c[2 * n - 1] = mpn_mul_1 (c + n - 1, a, n, B); + f += h + GMP_NUMB_BITS; + if ((c[2 * n - 1] & MPFR_LIMB_HIGHBIT) == 0) + { /* shift A by one bit to the left */ + mpn_lshift (a, c + n, n, 1); + a[0] |= mpn_lshift (c + n - 1, c + n - 1, 1, 1); + f --; + } + else + { + MPN_COPY (a, c + n, n); + if (error != t) + err_s_ab ++; + } + if ((error == t) && (c[n - 1] != 0)) + error = i; + } + } + + MPFR_TMP_FREE(marker); + + *exp_r = f; + + if (error == t) + return -1; /* result is exact */ + else /* error <= t-2 <= GMP_NUMB_BITS-2 + err_s_ab, err_s_a2 <= t-1 */ + { + /* if there are p loops after the first inexact result, with + j shifts in a^2 and l shifts in a*b, then the final error is + at most 2^(p+ceil((j+1)/2)+l+1)*ulp(res). + This is bounded by 2^(5/2*t-1/2) where t is the number of bits of e. + */ + error = error + err_s_ab + err_s_a2 / 2 + 3; /* <= 5t/2-1/2 */ +#if 0 + if ((error - 1) >= ((n * GMP_NUMB_BITS - 1) / 2)) + error = n * GMP_NUMB_BITS; /* result is completely wrong: + this is very unlikely since error is + at most 5/2*log_2(e), and + n * GMP_NUMB_BITS is at least + 3*log_2(e) */ +#endif + return error; + } +} |