[digamma.c] new function mpfr_digamma

[lngamma.c,li2.c] factored computation of Bernoulli numbers in new file
		  bernoulli.c (also used by digamma.c)


git-svn-id: svn://scm.gforge.inria.fr/svn/mpfr/trunk@6398 280ebfd0-de03-0410-8827-d642c229c3f4

11 files changed, 520 insertions, 118 deletions

diff --git a/Makefile.am b/Makefile.am
index 461cad16c..d96c0aaac 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -23,7 +23,7 @@ include_HEADERS = mpfr.h mpf2mpfr.h
 
 lib_LTLIBRARIES = libmpfr.la
 
-libmpfr_la_SOURCES = mpfr.h mpf2mpfr.h mpfr-gmp.h mpfr-impl.h mpfr-longlong.h mpfr-thread.h exceptions.c extract.c uceil_exp2.c uceil_log2.c ufloor_log2.c add.c add1.c add_ui.c agm.c clear.c cmp.c cmp_abs.c cmp_si.c cmp_ui.c comparisons.c div_2exp.c div_2si.c div_2ui.c div.c div_ui.c dump.c eq.c exp10.c exp2.c exp3.c exp.c frac.c get_d.c get_exp.c get_str.c init.c inp_str.c isinteger.c isinf.c isnan.c isnum.c const_log2.c log.c modf.c mul_2exp.c mul_2si.c mul_2ui.c mul.c mul_ui.c neg.c next.c out_str.c printf.c vasprintf.c const_pi.c pow.c pow_si.c pow_ui.c print_raw.c print_rnd_mode.c reldiff.c round_prec.c set.c setmax.c setmin.c set_d.c set_dfl_prec.c set_exp.c set_rnd.c set_f.c set_prc_raw.c set_prec.c set_q.c set_si.c set_str.c set_str_raw.c set_ui.c set_z.c sqrt.c sqrt_ui.c sub.c sub1.c sub_ui.c rint.c ui_div.c ui_sub.c urandomb.c get_z_exp.c swap.c  factorial.c cosh.c sinh.c tanh.c sinh_cosh.c acosh.c asinh.c atanh.c atan.c cmp2.c exp_2.c asin.c const_euler.c cos.c sin.c tan.c fma.c fms.c hypot.c log1p.c expm1.c log2.c log10.c ui_pow.c ui_pow_ui.c minmax.c dim.c signbit.c copysign.c setsign.c gmp_op.c init2.c acos.c sin_cos.c set_nan.c set_inf.c set_zero.c powerof2.c gamma.c set_ld.c get_ld.c cbrt.c volatile.c fits_s.h fits_sshort.c fits_sint.c fits_slong.c fits_u.h fits_ushort.c fits_uint.c fits_ulong.c fits_uintmax.c fits_intmax.c get_si.c get_ui.c zeta.c cmp_d.c erf.c inits.c inits2.c clears.c sgn.c check.c sub1sp.c version.c mpn_exp.c mpfr-gmp.c mp_clz_tab.c sum.c add1sp.c free_cache.c si_op.c cmp_ld.c set_ui_2exp.c set_si_2exp.c set_uj.c set_sj.c get_sj.c get_uj.c get_z.c iszero.c cache.c sqr.c int_ceil_log2.c isqrt.c strtofr.c pow_z.c logging.c mulders.c get_f.c round_p.c erfc.c atan2.c subnormal.c const_catalan.c root.c gen_inverse.h sec.c csc.c cot.c eint.c sech.c csch.c coth.c round_near_x.c constant.c abort_prec_max.c stack_interface.c lngamma.c zeta_ui.c set_d64.c get_d64.c jn.c yn.c rem1.c get_patches.c add_d.c sub_d.c d_sub.c mul_d.c div_d.c d_div.c li2.c rec_sqrt.c min_prec.c buildopt.c
+libmpfr_la_SOURCES = mpfr.h mpf2mpfr.h mpfr-gmp.h mpfr-impl.h mpfr-longlong.h mpfr-thread.h exceptions.c extract.c uceil_exp2.c uceil_log2.c ufloor_log2.c add.c add1.c add_ui.c agm.c clear.c cmp.c cmp_abs.c cmp_si.c cmp_ui.c comparisons.c div_2exp.c div_2si.c div_2ui.c div.c div_ui.c dump.c eq.c exp10.c exp2.c exp3.c exp.c frac.c get_d.c get_exp.c get_str.c init.c inp_str.c isinteger.c isinf.c isnan.c isnum.c const_log2.c log.c modf.c mul_2exp.c mul_2si.c mul_2ui.c mul.c mul_ui.c neg.c next.c out_str.c printf.c vasprintf.c const_pi.c pow.c pow_si.c pow_ui.c print_raw.c print_rnd_mode.c reldiff.c round_prec.c set.c setmax.c setmin.c set_d.c set_dfl_prec.c set_exp.c set_rnd.c set_f.c set_prc_raw.c set_prec.c set_q.c set_si.c set_str.c set_str_raw.c set_ui.c set_z.c sqrt.c sqrt_ui.c sub.c sub1.c sub_ui.c rint.c ui_div.c ui_sub.c urandomb.c get_z_exp.c swap.c  factorial.c cosh.c sinh.c tanh.c sinh_cosh.c acosh.c asinh.c atanh.c atan.c cmp2.c exp_2.c asin.c const_euler.c cos.c sin.c tan.c fma.c fms.c hypot.c log1p.c expm1.c log2.c log10.c ui_pow.c ui_pow_ui.c minmax.c dim.c signbit.c copysign.c setsign.c gmp_op.c init2.c acos.c sin_cos.c set_nan.c set_inf.c set_zero.c powerof2.c gamma.c set_ld.c get_ld.c cbrt.c volatile.c fits_s.h fits_sshort.c fits_sint.c fits_slong.c fits_u.h fits_ushort.c fits_uint.c fits_ulong.c fits_uintmax.c fits_intmax.c get_si.c get_ui.c zeta.c cmp_d.c erf.c inits.c inits2.c clears.c sgn.c check.c sub1sp.c version.c mpn_exp.c mpfr-gmp.c mp_clz_tab.c sum.c add1sp.c free_cache.c si_op.c cmp_ld.c set_ui_2exp.c set_si_2exp.c set_uj.c set_sj.c get_sj.c get_uj.c get_z.c iszero.c cache.c sqr.c int_ceil_log2.c isqrt.c strtofr.c pow_z.c logging.c mulders.c get_f.c round_p.c erfc.c atan2.c subnormal.c const_catalan.c root.c gen_inverse.h sec.c csc.c cot.c eint.c sech.c csch.c coth.c round_near_x.c constant.c abort_prec_max.c stack_interface.c lngamma.c zeta_ui.c set_d64.c get_d64.c jn.c yn.c rem1.c get_patches.c add_d.c sub_d.c d_sub.c mul_d.c div_d.c d_div.c li2.c rec_sqrt.c min_prec.c buildopt.c bernoulli.c digamma.c
 
 libmpfr_la_LIBADD = @LIBOBJS@
 
diff --git a/NEWS b/NEWS
index f812e9489..2b35e2c72 100644
--- a/NEWS
+++ b/NEWS
@@ -32,6 +32,7 @@ _ The rounding mode type mp_rnd_t is now mpfr_rnd_t (mp_rnd_t kept for
 - New functions mpfr_buildopt_tls_p and mpfr_buildopt_decimal_p giving
   information about options used at MPFR build time.
 - New function mpfr_set_zero.
+- New function mpfr_digamma.
 - Some documentation files are installed in $docdir.
 - Bug fixes.
 
diff --git a/algorithms.tex b/algorithms.tex
index c6cb326b2..1aca1238d 100644
--- a/algorithms.tex
+++ b/algorithms.tex
@@ -3946,6 +3946,22 @@ where
 3 - \Exp(t))
 \end{eqnarray*}
 
+\subsection{The Digamma Function}
+
+The Digamma function \texttt{mpfr\_digamma} is defined by:
+\[ \psi(x) = \frac{d}{dx} \log\Gamma(x), \]
+and is computed from the asymptotic series \cite{Smith01}
+\[ \psi(x) \sim \log x - \frac{1}{2x} - \sum_{n=1}^{\infty}
+   \frac{B_{2n}}{2n x^{2n}}. \]
+(We assume the error in the sum is bounded by the first neglected term.)
+Since $B_{2n} \approx 2 (2n)!/(2\pi)^{-2n}$, the terms of the sum decrease
+until $n \approx \pi x$, and then the error term is $\approx e^{-2\pi x}$.
+If $x$ is too small with respect to the target precision, we use the formula
+\cite{Smith01}:
+\[ \psi(x+j) = \frac{1}{x+j-1} + \frac{1}{x+j-2} + \cdots + \frac{1}{x} +
+\psi(x), \]
+and compute $\psi(x+j)$ instead with the asymptotic formula.
+
 \subsection{Radix Conversion}
 
 The \texttt{mpfr\_get\_str} function with size $0$ and base $b$ chooses an
diff --git a/bernoulli.c b/bernoulli.c
new file mode 100644
index 000000000..b6a8adf31
--- /dev/null
+++ b/bernoulli.c
@@ -0,0 +1,78 @@
+/* bernoulli -- auxiliary function to compute Bernoulli numbers.
+
+Copyright 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+Contributed by the Arenaire and Cacao projects, INRIA.
+
+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. */
+
+/* assuming b[0]...b[2(n-1)] are computed, computes and stores B[2n]*(2n+1)!
+
+   t/(exp(t)-1) = sum(B[j]*t^j/j!, j=0..infinity)
+   thus t = (exp(t)-1) * sum(B[j]*t^j/j!, n=0..infinity).
+   Taking the coefficient of degree n+1 > 1, we get:
+   0 = sum(1/(n+1-k)!*B[k]/k!, k=0..n)
+   which gives:
+   B[n] = -sum(binomial(n+1,k)*B[k], k=0..n-1)/(n+1).
+
+   Let C[n] = B[n]*(n+1)!.
+   Then C[n] = -sum(binomial(n+1,k)*C[k]*n!/(k+1)!,  k=0..n-1),
+   which proves that the C[n] are integers.
+*/
+static mpz_t*
+bernoulli (mpz_t *b, unsigned long n)
+{
+  if (n == 0)
+    {
+      b = (mpz_t *) (*__gmp_allocate_func) (sizeof (mpz_t));
+      mpz_init_set_ui (b[0], 1);
+    }
+  else
+    {
+      mpz_t t;
+      unsigned long k;
+
+      b = (mpz_t *) (*__gmp_reallocate_func)
+        (b, n * sizeof (mpz_t), (n + 1) * sizeof (mpz_t));
+      mpz_init (b[n]);
+      /* b[n] = -sum(binomial(2n+1,2k)*C[k]*(2n)!/(2k+1)!,  k=0..n-1) */
+      mpz_init_set_ui (t, 2 * n + 1);
+      mpz_mul_ui (t, t, 2 * n - 1);
+      mpz_mul_ui (t, t, 2 * n);
+      mpz_mul_ui (t, t, n);
+      mpz_fdiv_q_ui (t, t, 3); /* exact: t=binomial(2*n+1,2*k)*(2*n)!/(2*k+1)!
+                               for k=n-1 */
+      mpz_mul (b[n], t, b[n-1]);
+      for (k = n - 1; k-- > 0;)
+        {
+          mpz_mul_ui (t, t, 2 * k + 1);
+          mpz_mul_ui (t, t, 2 * k + 2);
+          mpz_mul_ui (t, t, 2 * k + 2);
+          mpz_mul_ui (t, t, 2 * k + 3);
+          mpz_fdiv_q_ui (t, t, 2 * (n - k) + 1);
+          mpz_fdiv_q_ui (t, t, 2 * (n - k));
+          mpz_addmul (b[n], t, b[k]);
+        }
+      /* take into account C[1] */
+      mpz_mul_ui (t, t, 2 * n + 1);
+      mpz_fdiv_q_2exp (t, t, 1);
+      mpz_sub (b[n], b[n], t);
+      mpz_neg (b[n], b[n]);
+      mpz_clear (t);
+    }
+  return b;
+}
diff --git a/digamma.c b/digamma.c
new file mode 100644
index 000000000..3b4424d6b
--- /dev/null
+++ b/digamma.c
@@ -0,0 +1,373 @@
+/* mpfr_digamma -- digamma function of a floating-point number
+
+Copyright 2009 Free Software Foundation, Inc.
+Contributed by the Arenaire and Cacao projects, INRIA.
+
+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. */
+
+#include "mpfr-impl.h"
+#include "bernoulli.c"
+
+/* Put in s an approximation of digamma(x).
+   Assumes x >= 2.
+   Assumes s does not overlap with x.
+   Returns an integer e such that the error is bounded by 2^e ulps
+   of the result s.
+*/
+static mp_exp_t
+mpfr_digamma_approx (mpfr_ptr s, mpfr_srcptr x)
+{
+  mp_prec_t p = MPFR_PREC (s);
+  mpfr_t t, u, invxx;
+  mp_exp_t e, exps, f, expu;
+  mpz_t *INITIALIZED(B);  /* variable B declared as initialized */
+  unsigned long n0, n; /* number of allocated B[] */
+
+  MPFR_ASSERTN(MPFR_IS_POS(x) && (MPFR_EXP(x) >= 2));
+
+  mpfr_init2 (t, p);
+  mpfr_init2 (u, p);
+  mpfr_init2 (invxx, p);
+
+  mpfr_log (s, x, MPFR_RNDN);         /* error <= 1/2 ulp */
+  mpfr_ui_div (t, 1, x, MPFR_RNDN);   /* error <= 1/2 ulp */
+  mpfr_div_2exp (t, t, 1, MPFR_RNDN); /* exact */
+  mpfr_sub (s, s, t, MPFR_RNDN);
+  /* error <= 1/2 + 1/2*2^(EXP(olds)-EXP(s)) + 1/2*2^(EXP(t)-EXP(s)).
+     For x >= 2, log(x) >= 2*(1/(2x)), thus olds >= 2t, and olds - t >= olds/2,
+     thus 0 <= EXP(olds)-EXP(s) <= 1, and EXP(t)-EXP(s) <= 0, thus
+     error <= 1/2 + 1/2*2 + 1/2 <= 2 ulps. */
+  e = 2; /* initial error */
+  mpfr_mul (invxx, x, x, MPFR_RNDZ);     /* invxx = x^2 * (1 + theta)
+                                            for |theta| <= 2^(-p) */
+  mpfr_ui_div (invxx, 1, invxx, MPFR_RNDU); /* invxx = 1/x^2 * (1 + theta)^2 */
+
+  /* in the following we note err=xxx when the ratio between the approximation
+     and the exact result can be written (1 + theta)^xxx for |theta| <= 2^(-p),
+     following Higham's method */
+  B = bernoulli ((mpz_t *) 0, 0);
+  mpfr_set_ui (t, 1, MPFR_RNDN); /* err = 0 */
+  for (n = 1;; n++)
+    {
+      /* compute next Bernoulli number */
+      B = bernoulli (B, n);
+      /* The main term is Bernoulli[2n]/(2n)/x^(2n) = B[n]/(2n+1)!(2n)/x^(2n)
+         = B[n]*t[n]/(2n) where t[n]/t[n-1] = 1/(2n)/(2n+1)/x^2. */
+      mpfr_mul (t, t, invxx, MPFR_RNDU);        /* err = err + 3 */
+      mpfr_div_ui (t, t, 2 * n, MPFR_RNDU);     /* err = err + 1 */
+      mpfr_div_ui (t, t, 2 * n + 1, MPFR_RNDU); /* err = err + 1 */
+      /* we thus have err = 5n here */
+      mpfr_div_ui (u, t, 2 * n, MPFR_RNDU);     /* err = 5n+1 */
+      mpfr_mul_z (u, u, B[n], MPFR_RNDU);       /* err = 5n+2, and the
+                                                   absolute error is bounded
+                                                   by 10n+4 ulp(u) [Rule 11] */
+      /* if the terms 'u' are decreasing by a factor two at least,
+         then the error coming from those is bounded by
+         sum((10n+4)/2^n, n=1..infinity) = 24 */
+      exps = mpfr_get_exp (s);
+      expu = mpfr_get_exp (u);
+      if (expu < exps - (mp_exp_t) p)
+        break;
+      mpfr_sub (s, s, u, MPFR_RNDN); /* error <= 24 + n/2 */
+      if (mpfr_get_exp (s) < exps)
+        e <<= exps - mpfr_get_exp (s);
+      e ++; /* error in mpfr_sub */
+      f = 10 * n + 4;
+      while (expu < exps)
+        {
+          f = (1 + f) / 2;
+          expu ++;
+        }
+      e += f; /* total rouding error coming from 'u' term */
+    }
+
+  n0 = ++n;
+  while (n--)
+    mpz_clear (B[n]);
+  (*__gmp_free_func) (B, n0 * sizeof (mpz_t));
+
+  mpfr_clear (t);
+  mpfr_clear (u);
+  mpfr_clear (invxx);
+
+  f = 0;
+  while (e > 1)
+    {
+      f++;
+      e = (e + 1) / 2;
+      /* Invariant: 2^f * e does not decrease */
+    }
+  return f;
+}
+
+/* Use the reflection formula Digamma(1-x) = Digamma(x) + Pi * cot(Pi*x),
+   i.e., Digamma(x) = Digamma(1-x) - Pi * cot(Pi*x).
+   Assume x < 1/2. */
+static int
+mpfr_digamma_reflection (mpfr_ptr y, mpfr_srcptr x, mpfr_rnd_t rnd_mode)
+{
+  mp_prec_t p = MPFR_PREC(y) + 10, q;
+  mpfr_t t, u, v;
+  mp_exp_t e1, expv;
+  int inex;
+  MPFR_ZIV_DECL (loop);
+
+  /* we want that 1-x is exact with precision q: if 0 < x < 1/2, then
+     q = PREC(x)-EXP(x) is ok, otherwise if -1 <= x < 0, q = PREC(x)-EXP(x)
+     is ok, otherwise for x < -1, PREC(x) is ok if EXP(x) <= PREC(x),
+     otherwise we need EXP(x) */
+  if (MPFR_EXP(x) < 0)
+    q = MPFR_PREC(x) + 1 - MPFR_EXP(x);
+  else if (MPFR_EXP(x) <= MPFR_PREC(x))
+    q = MPFR_PREC(x) + 1;
+  else
+    q = MPFR_EXP(x);
+  mpfr_init2 (u, q);
+  MPFR_ASSERTN(mpfr_ui_sub (u, 1, x, MPFR_RNDN) == 0);
+
+  /* if x is half an integer, cot(Pi*x) = 0, thus Digamma(x) = Digamma(1-x) */
+  mpfr_mul_2exp (u, u, 1, MPFR_RNDN);
+  inex = mpfr_integer_p (u);
+  mpfr_div_2exp (u, u, 1, MPFR_RNDN);
+  if (inex)
+    {
+      inex = mpfr_digamma (y, u, rnd_mode);
+      goto end;
+    }
+
+  mpfr_init2 (t, p);
+  mpfr_init2 (v, p);
+
+  MPFR_ZIV_INIT (loop, p);
+  for (;;)
+    {
+      mpfr_const_pi (v, MPFR_RNDN);  /* v = Pi*(1+theta) for |theta|<=2^(-p) */
+      mpfr_mul (t, v, x, MPFR_RNDN); /* (1+theta)^2 */
+      e1 = MPFR_EXP(t) - (mp_exp_t) p + 1; /* bound for t: err(t) <= 2^e1 */
+      mpfr_cot (t, t, MPFR_RNDN);
+      /* cot(t * (1+h)) = cot(t) - theta * (1 + cot(t)^2) with |theta|<=t*h */
+      if (MPFR_EXP(t) > 0)
+        e1 = e1 + 2 * MPFR_EXP(t) + 1;
+      else
+        e1 = e1 + 1;
+      /* now theta * (1 + cot(t)^2) <= 2^e1 */
+      e1 += (mp_exp_t) p - MPFR_EXP(t); /* error is now 2^e1 ulps */
+      mpfr_mul (t, t, v, MPFR_RNDN);
+      e1 ++;
+      mpfr_digamma (v, u, MPFR_RNDN);   /* error <= 1/2 ulp */
+      expv = MPFR_EXP(v);
+      mpfr_sub (v, v, t, MPFR_RNDN);
+      if (MPFR_EXP(v) < MPFR_EXP(t))
+        e1 += MPFR_EXP(t) - MPFR_EXP(v); /* scale error for t wrt new v */
+      /* now take into account the 1/2 ulp error for v */
+      if (expv - MPFR_EXP(v) - 1 > e1)
+        e1 = expv - MPFR_EXP(v) - 1;
+      else
+        e1 ++;
+      e1 ++; /* rounding error for mpfr_sub */
+      if (MPFR_CAN_ROUND (v, p - e1, MPFR_PREC(y), rnd_mode))
+        break;
+      MPFR_ZIV_NEXT (loop, p);
+      mpfr_set_prec (t, p);
+      mpfr_set_prec (v, p);
+    }
+  MPFR_ZIV_FREE (loop);
+
+  inex = mpfr_set (y, v, rnd_mode);
+
+  mpfr_clear (t);
+  mpfr_clear (v);
+ end:
+  mpfr_clear (u);
+
+  return inex;
+}
+
+/* we have x >= 1/2 here */
+static int
+mpfr_digamma_positive (mpfr_ptr y, mpfr_srcptr x, mpfr_rnd_t rnd_mode)
+{
+  mp_prec_t p = MPFR_PREC(y) + 10, q;
+  mpfr_t t, u, x_plus_j;
+  int inex;
+  mp_exp_t errt, erru, expt;
+  unsigned long j = 0, min;
+  MPFR_ZIV_DECL (loop);
+
+  /* compute a precision q such that x+1 is exact */
+  if (MPFR_PREC(x) < MPFR_EXP(x))
+    q = MPFR_EXP(x);
+  else
+    q = MPFR_PREC(x) + 1;
+  mpfr_init2 (x_plus_j, q);
+  
+  mpfr_init2 (t, p);
+  mpfr_init2 (u, p);
+  MPFR_ZIV_INIT (loop, p);
+  for(;;)
+    {
+      /* Lower bound for x+j in mpfr_digamma_approx call: since the smallest
+         term of the divergent series for Digamma(x) is about exp(-2*Pi*x), and
+         we want it to be less than 2^(-p), this gives x > p*log(2)/(2*Pi)
+         i.e., x >= 0.1103 p.
+         To be safe, we ensure x >= 0.25 * p.
+      */
+      min = (p + 3) / 4;
+      if (min < 2)
+        min = 2;
+
+      mpfr_set (x_plus_j, x, MPFR_RNDN);
+      mpfr_set_ui (u, 0, MPFR_RNDN);
+      j = 0;
+      while (mpfr_cmp_ui (x_plus_j, min) < 0)
+        {
+          j ++;
+          mpfr_ui_div (t, 1, x_plus_j, MPFR_RNDN); /* err <= 1/2 ulp */
+          mpfr_add (u, u, t, MPFR_RNDN);
+          inex = mpfr_add_ui (x_plus_j, x_plus_j, 1, MPFR_RNDZ);
+          if (inex != 0) /* we lost one bit */
+            {
+              q ++;
+              mpfr_prec_round (x_plus_j, q, MPFR_RNDZ);
+              mpfr_nextabove (x_plus_j);
+            }
+          /* since all terms are positive, the error is bounded by j ulps */
+        }
+      for (erru = 0; j > 1; erru++, j = (j + 1) / 2);
+      errt = mpfr_digamma_approx (t, x_plus_j);
+      expt = MPFR_EXP(t);
+      mpfr_sub (t, t, u, MPFR_RNDN);
+      if (MPFR_EXP(t) < expt)
+        errt += expt - MPFR_EXP(t);
+      if (MPFR_EXP(t) < MPFR_EXP(u))
+        erru += MPFR_EXP(u) - MPFR_EXP(t);
+      if (errt > erru)
+        errt = errt + 1;
+      else if (errt == erru)
+        errt = errt + 2;
+      else
+        errt = erru + 1;
+      if (MPFR_CAN_ROUND (t, p - errt, MPFR_PREC(y), rnd_mode))
+        break;
+      MPFR_ZIV_NEXT (loop, p);
+      mpfr_set_prec (t, p);
+      mpfr_set_prec (u, p);
+    }
+  MPFR_ZIV_FREE (loop);
+  inex = mpfr_set (y, t, rnd_mode);
+  mpfr_clear (t);
+  mpfr_clear (u);
+  mpfr_clear (x_plus_j);
+  return inex;
+}
+
+int
+mpfr_digamma (mpfr_ptr y, mpfr_srcptr x, mpfr_rnd_t rnd_mode)
+{
+  int inex;
+  MPFR_SAVE_EXPO_DECL (expo);
+
+  if (MPFR_UNLIKELY(MPFR_IS_SINGULAR(x)))
+    {
+      if (MPFR_IS_NAN(x))
+        {
+          MPFR_SET_NAN(y);
+          MPFR_RET_NAN;
+        }
+      else if (MPFR_IS_INF(x))
+        {
+          if (MPFR_IS_POS(x)) /* Digamma(+Inf) = +Inf */
+            {
+              MPFR_SET_INF(y);
+              MPFR_RET(0);
+            }
+          else                /* Digamma(-Inf) = NaN */
+            {
+              MPFR_SET_NAN(y);
+              MPFR_RET_NAN;
+            }
+        }
+      else /* Zero case */
+        {
+          /* the following works also in case of overlap */
+          MPFR_SET_INF(y);
+          MPFR_SET_OPPOSITE_SIGN(y, x);
+          MPFR_RET(0);
+        }
+    }
+
+  /* now x is a normal number */
+
+  MPFR_SAVE_EXPO_MARK (expo);
+  /* for x very small, we have Digamma(x) = -1/x - gamma + O(x), more precisely
+     -1 < Digamma(x) + 1/x < 0 for -0.2 < x < 0.2, thus:
+     (i) either x is a power of two, then 1/x is exactly representable, and
+         as long as 1/2*ulp(1/x) > 1, we can conclude;
+     (ii) otherwise assume x has <= n bits, and y has <= n+1 bits, then
+   |y + 1/x| >= 2^(-2n) ufp(y), where ufp means unit in first place.
+   Since |Digamma(x) + 1/x| <= 1, if 2^(-2n) ufp(y) >= 2, then
+   |y - Digamma(x)| >= 2^(-2n-1)ufp(y), and rounding -1/x gives the correct result.
+   If x < 2^E, then y > 2^(-E), thus ufp(y) > 2^(-E-1).
+   A sufficient condition is thus EXP(x) <= -2 MAX(PREC(x),PREC(Y)). */
+  if (MPFR_EXP(x) < -2)
+    {
+      if (MPFR_EXP(x) <= -2 * (mp_exp_t) MAX(MPFR_PREC(x), MPFR_PREC(y)))
+        {
+          int signx = MPFR_SIGN(x);
+          inex = mpfr_si_div (y, -1, x, rnd_mode);
+          if (inex == 0) /* x is a power of two */
+            { /* result always -1/x, except when rounding down */
+              if (rnd_mode == MPFR_RNDA)
+                rnd_mode = (signx > 0) ? MPFR_RNDD : MPFR_RNDU;
+              if (rnd_mode == MPFR_RNDZ)
+                rnd_mode = (signx > 0) ? MPFR_RNDU : MPFR_RNDD;
+              if (rnd_mode == MPFR_RNDU)
+                inex = 1;
+              else if (rnd_mode == MPFR_RNDD)
+                {
+                  mpfr_nextbelow (y);
+                  inex = -1;
+                }
+              else /* nearest */
+                inex = 1;
+            }
+          MPFR_SAVE_EXPO_UPDATE_FLAGS (expo, __gmpfr_flags);
+          goto end;
+        }
+    }
+
+  /* Digamma is undefined for negative integers */
+  if (MPFR_IS_NEG(x))
+    {
+      if (mpfr_integer_p(x))
+        {
+          MPFR_SET_NAN(y);
+          MPFR_RET_NAN;
+        }
+      inex = mpfr_digamma_reflection (y, x, rnd_mode);
+    }
+  /* if x < 1/2 we use the reflection formula */
+  else if (MPFR_EXP(x) < 0)
+    inex = mpfr_digamma_reflection (y, x, rnd_mode);
+  else
+    inex = mpfr_digamma_positive (y, x, rnd_mode);
+
+ end:
+  MPFR_SAVE_EXPO_FREE (expo);
+  return mpfr_check_range (y, inex, rnd_mode);
+}
diff --git a/li2.c b/li2.c
index ed3cd326d..fb00ea56e 100644
--- a/li2.c
+++ b/li2.c
@@ -22,63 +22,7 @@ http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
 
 #define MPFR_NEED_LONGLONG_H
 #include "mpfr-impl.h"
-
-/* assuming B[0]...B[2(n-1)] are computed, computes and stores B[2n]*(2n+1)!
-
-   t/(exp(t)-1) = sum(B[j]*t^j/j!, j=0..infinity)
-   thus t = (exp(t)-1) * sum(B[j]*t^j/j!, n=0..infinity).
-   Taking the coefficient of degree n+1 > 1, we get:
-   0 = sum(1/(n+1-k)!*B[k]/k!, k=0..n)
-   which gives:
-   B[n] = -sum(binomial(n+1,k)*B[k], k=0..n-1)/(n+1).
-
-   Let C[n] = B[n]*(n+1)!.
-   Then C[n] = -sum(binomial(n+1,k)*C[k]*n!/(k+1)!,  k=0..n-1),
-   which proves that the C[n] are integers.
-*/
-static mpz_t *
-bernoulli (mpz_t * b, unsigned long n)
-{
-  if (n == 0)
-    {
-      b = (mpz_t *) (*__gmp_allocate_func) (sizeof (mpz_t));
-      mpz_init_set_ui (b[0], 1);
-    }
-  else
-    {
-      mpz_t t;
-      unsigned long k;
-
-      b = (mpz_t *) (*__gmp_reallocate_func)
-        (b, n * sizeof (mpz_t), (n + 1) * sizeof (mpz_t));
-      mpz_init (b[n]);
-      /* b[n] = -sum(binomial(2n+1,2k)*C[k]*(2n)!/(2k+1)!,  k=0..n-1) */
-      mpz_init_set_ui (t, 2 * n + 1);
-      mpz_mul_ui (t, t, 2 * n - 1);
-      mpz_mul_ui (t, t, 2 * n);
-      mpz_mul_ui (t, t, n);
-      mpz_fdiv_q_ui (t, t, 3);  /* exact: t=binomial(2*n+1,2*k)*(2*n)!/(2*k+1)!
-                                   for k=n-1 */
-      mpz_mul (b[n], t, b[n - 1]);
-      for (k = n - 1; k-- > 0;)
-        {
-          mpz_mul_ui (t, t, 2 * k + 1);
-          mpz_mul_ui (t, t, 2 * k + 2);
-          mpz_mul_ui (t, t, 2 * k + 2);
-          mpz_mul_ui (t, t, 2 * k + 3);
-          mpz_fdiv_q_ui (t, t, 2 * (n - k) + 1);
-          mpz_fdiv_q_ui (t, t, 2 * (n - k));
-          mpz_addmul (b[n], t, b[k]);
-        }
-      /* take into account C[1] */
-      mpz_mul_ui (t, t, 2 * n + 1);
-      mpz_fdiv_q_2exp (t, t, 1);
-      mpz_sub (b[n], b[n], t);
-      mpz_neg (b[n], b[n]);
-      mpz_clear (t);
-    }
-  return b;
-}
+#include "bernoulli.c"
 
 /* Compute the alternating series
    s = S(z) = \sum_{k=0}^infty B_{2k} (z))^{2k+1} / (2k+1)!
diff --git a/lngamma.c b/lngamma.c
index 5361eb919..2d7af2354 100644
--- a/lngamma.c
+++ b/lngamma.c
@@ -22,63 +22,7 @@ http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
 
 #define MPFR_NEED_LONGLONG_H
 #include "mpfr-impl.h"
-
-/* assuming b[0]...b[2(n-1)] are computed, computes and stores B[2n]*(2n+1)!
-
-   t/(exp(t)-1) = sum(B[j]*t^j/j!, j=0..infinity)
-   thus t = (exp(t)-1) * sum(B[j]*t^j/j!, n=0..infinity).
-   Taking the coefficient of degree n+1 > 1, we get:
-   0 = sum(1/(n+1-k)!*B[k]/k!, k=0..n)
-   which gives:
-   B[n] = -sum(binomial(n+1,k)*B[k], k=0..n-1)/(n+1).
-
-   Let C[n] = B[n]*(n+1)!.
-   Then C[n] = -sum(binomial(n+1,k)*C[k]*n!/(k+1)!,  k=0..n-1),
-   which proves that the C[n] are integers.
-*/
-static mpz_t*
-bernoulli (mpz_t *b, unsigned long n)
-{
-  if (n == 0)
-    {
-      b = (mpz_t *) (*__gmp_allocate_func) (sizeof (mpz_t));
-      mpz_init_set_ui (b[0], 1);
-    }
-  else
-    {
-      mpz_t t;
-      unsigned long k;
-
-      b = (mpz_t *) (*__gmp_reallocate_func)
-        (b, n * sizeof (mpz_t), (n + 1) * sizeof (mpz_t));
-      mpz_init (b[n]);
-      /* b[n] = -sum(binomial(2n+1,2k)*C[k]*(2n)!/(2k+1)!,  k=0..n-1) */
-      mpz_init_set_ui (t, 2 * n + 1);
-      mpz_mul_ui (t, t, 2 * n - 1);
-      mpz_mul_ui (t, t, 2 * n);
-      mpz_mul_ui (t, t, n);
-      mpz_fdiv_q_ui (t, t, 3); /* exact: t=binomial(2*n+1,2*k)*(2*n)!/(2*k+1)!
-                               for k=n-1 */
-      mpz_mul (b[n], t, b[n-1]);
-      for (k = n - 1; k-- > 0;)
-        {
-          mpz_mul_ui (t, t, 2 * k + 1);
-          mpz_mul_ui (t, t, 2 * k + 2);
-          mpz_mul_ui (t, t, 2 * k + 2);
-          mpz_mul_ui (t, t, 2 * k + 3);
-          mpz_fdiv_q_ui (t, t, 2 * (n - k) + 1);
-          mpz_fdiv_q_ui (t, t, 2 * (n - k));
-          mpz_addmul (b[n], t, b[k]);
-        }
-      /* take into account C[1] */
-      mpz_mul_ui (t, t, 2 * n + 1);
-      mpz_fdiv_q_2exp (t, t, 1);
-      mpz_sub (b[n], b[n], t);
-      mpz_neg (b[n], b[n]);
-      mpz_clear (t);
-    }
-  return b;
-}
+#include "bernoulli.c"
 
 /* given a precision p, return alpha, such that the argument reduction
    will use k = alpha*p*log(2).
diff --git a/mpfr.h b/mpfr.h
index 3ae7538dc..c709f99ff 100644
--- a/mpfr.h
+++ b/mpfr.h
@@ -619,6 +619,7 @@ __MPFR_DECLSPEC int mpfr_root _MPFR_PROTO ((mpfr_ptr,mpfr_srcptr,unsigned long,m
 __MPFR_DECLSPEC int mpfr_gamma _MPFR_PROTO((mpfr_ptr,mpfr_srcptr,mpfr_rnd_t));
 __MPFR_DECLSPEC int mpfr_lngamma _MPFR_PROTO((mpfr_ptr,mpfr_srcptr,mpfr_rnd_t));
 __MPFR_DECLSPEC int mpfr_lgamma _MPFR_PROTO((mpfr_ptr,int*,mpfr_srcptr,mpfr_rnd_t));
+__MPFR_DECLSPEC int mpfr_digamma _MPFR_PROTO((mpfr_ptr,mpfr_srcptr,mpfr_rnd_t));
 __MPFR_DECLSPEC int mpfr_zeta _MPFR_PROTO ((mpfr_ptr,mpfr_srcptr,mpfr_rnd_t));
 __MPFR_DECLSPEC int mpfr_zeta_ui _MPFR_PROTO ((mpfr_ptr,unsigned long,mpfr_rnd_t));
 __MPFR_DECLSPEC int mpfr_fac_ui _MPFR_PROTO ((mpfr_ptr, unsigned long int,
diff --git a/mpfr.texi b/mpfr.texi
index 6e41ca599..086976d4b 100644
--- a/mpfr.texi
+++ b/mpfr.texi
@@ -1827,6 +1827,12 @@ by @var{signp}. When @var{op} is an infinity or a non-positive integer,
 the sign of the zero.
 @end deftypefun
 
+@deftypefun int mpfr_digamma (mpfr_t @var{rop}, mpfr_t @var{op}, mpfr_rnd_t @var{rnd})
+Set @var{rop} to the value of the Digamma (sometimes also called Psi)
+function on @var{op}, rounded in the direction @var{rnd}.
+When @var{op} is a negative integer, NaN is returned.
+@end deftypefun
+
 @deftypefun int mpfr_zeta (mpfr_t @var{rop}, mpfr_t @var{op}, mpfr_rnd_t @var{rnd})
 @deftypefunx int mpfr_zeta_ui (mpfr_t @var{rop}, unsigned long @var{op}, mpfr_rnd_t @var{rnd})
 Set @var{rop} to the value of the Riemann Zeta function on @var{op},
diff --git a/tests/Makefile.am b/tests/Makefile.am
index adb33ba97..212496965 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -18,9 +18,9 @@ check_PROGRAMS = tversion tinternals tinits tisqrt tsgn		\
      tcan_round tcbrt tcmp tcmp2 tcmp_d tcmp_ld tcmp_ui		\
      tcmpabs tcomparisons tconst_catalan tconst_euler		\
      tconst_log2 tconst_pi tcopysign tcos tcosh tcot tcoth	\
-     tcsc tcsch td_div td_sub tdim tdiv tdiv_d tdiv_ui teint	\
-     teq terf texp texp10 texp2 texpm1 tfactorial tfits tfma	\
-     tfmod tfms tfprintf tfrac tgamma tget_d tget_d_2exp	\
+     tcsc tcsch td_div td_sub tdigamma tdim tdiv tdiv_d tdiv_ui \
+     teint teq terf texp texp10 texp2 texpm1 tfactorial tfits   \
+     tfma tfmod tfms tfprintf tfrac tgamma tget_d tget_d_2exp	\
      tget_f tget_ld_2exp tget_set_d64 tget_sj tget_str		\
      tget_z tgmpop thyperbolic thypot tinp_str tj0 tj1 tjn	\
      tl2b tlgamma tli2 tlngamma tlog tlog10 tlog1p tlog2	\
diff --git a/tests/tdigamma.c b/tests/tdigamma.c
new file mode 100644
index 000000000..0507b4c7f
--- /dev/null
+++ b/tests/tdigamma.c
@@ -0,0 +1,39 @@
+/* test file for digamma function
+
+Copyright 2009 Free Software Foundation, Inc.
+Contributed by the Arenaire and Cacao projects, INRIA.
+
+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. */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "mpfr-test.h"
+
+#define TEST_FUNCTION mpfr_digamma
+#include "tgeneric.c"
+
+int
+main (int argc, char *argv[])
+{
+  tests_start_mpfr ();
+
+  test_generic (2, 100, 2);
+
+  tests_end_mpfr ();
+  return 0;
+}
+