implemented asymptotic expansion for large argument in j0/j1/jn

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

5 files changed, 280 insertions, 1 deletions

diff --git a/algorithms.tex b/algorithms.tex
index bf0f702d4..ef191c6f4 100644
--- a/algorithms.tex
+++ b/algorithms.tex
@@ -3043,7 +3043,9 @@ is an exponent loss in the final subtraction $r = \circ(v_{n+1}-w)$.
 
 The Bessel function $J_n(z)$ of first kind and integer order $n$
 is defined as follows \cite[Eq.~(9.1.10)]{AbSt73}:
-\[ J_n(z) = (z/2)^n \sum_{k=0}^{\infty} \frac{(-z^2/4)^k}{k! (k+n)!}. \]
+\begin{equation} \label{Jn_0}
+J_n(z) = (z/2)^n \sum_{k=0}^{\infty} \frac{(-z^2/4)^k}{k! (k+n)!}.
+\end{equation}
 It is real for all real $z$, tends to $0$ by oscillating around $0$ when
 $z \rightarrow \pm\infty$, and tends to $0$ when $z \rightarrow 0$, except
 $J_0$ which tends to $1$.
@@ -3094,6 +3096,52 @@ Together with $n! \geq \sqrt{2 \pi n} (n/e)^n$, which follows from example
 from \cite[Eq.~6.1.38]{AbSt73}, this gives:
 \[ |J_n(z)| \leq \frac{1}{\sqrt{2 \pi n}} \left( \frac{ze}{2n} \right)^n. \]
 
+\paragraph{Large argument.}
+
+For large argument $z$, formula (\ref{Jn_0}) requires at least 
+$k \approx z/2$ terms before starting to converge. If $k \leq z/2$, it is
+better to use formula 9.2.5 from \cite{AbSt73}, which
+provides at least $2$ bits per term:
+\[ J_n(z) = \sqrt{\frac{2}{\pi z}} [P(n,z) \cos \chi - Q(n,z) \sin \chi], \]
+where $\chi = z - (n/2 + 1/4) \pi$, and $P(n,z)$ and $Q(n,z)$ are two
+diverging series:
+\begin{small}
+\[ P(n,z) \approx \sum_{k=0}^{\infty} (-1)^k \frac{\Gamma(1/2+n+2k) (2z)^{-2k}}
+   {(2k)! \Gamma(1/2+n-2k)}, \quad
+   Q(n,z) \approx \sum_{k=0}^{\infty} (-1)^k \frac{\Gamma(1/2+n+2k+1) (2z)^{-2k-1}}
+   {(2k+1)! \Gamma(1/2+n-2k-1)}. \]
+\end{small}
+% P:=proc(n,z) add((-1)^k*GAMMA(1/2+n+2*k)/(2*k)!/GAMMA(1/2+n-2*k)/
+% (2*z)^(2*k),k=0..4) end:
+% Q:=proc(n,z) add((-1)^k*GAMMA(1/2+n+2*k+1)/(2*k+1)!/GAMMA(1/2+n-2*k-1)/
+% (2*z)^(2*k+1),k=0..4) end:
+% J:=proc(n,z) sqrt(2/Pi/z)*(P(n,z)*cos(z-(n/2+1/4)*Pi)-Q(n,z)*
+% sin(z-(n/2+1/4)*Pi)) end:
+If $n$ is real and non-negative --- which is the case here ---,
+the remainder of $P(n,z)$ after $k$ terms does not exceed the $(k+1)$th term
+and is of the same sign, provided $k > n/2 - 1/4$; the same holds for
+$Q(n,z)$ as long as $k > n/2 - 3/4$ \cite[9.2.10]{AbSt73}.
+
+If we first approximate $\chi = z - (n/2 + 1/4) \pi$ with working precision 
+$w$, and then approximate $\cos \chi$ and $\sin \chi$, there will be a huge
+relative error if $z > 2^w$. Instead, we use the fact that for $n$ even,
+\[ P(n,z) \cos \chi - Q(n,z) \sin \chi = \frac{1}{\sqrt{2}} (-1)^{n/2}
+   [P (\sin z + \cos z) + Q (\cos z - \sin z)], \]
+and for $n$ odd,
+\[ P(n,z) \cos \chi - Q(n,z) \sin \chi = \frac{1}{\sqrt{2}} (-1)^{(n-1)/2}
+   [P (\sin z - \cos z) + Q (\cos z + \sin z)], \]
+where $\cos z$ and $\sin z$ are computed accurately with 
+\texttt{mpfr\_sin\_cos}, which uses in turn \texttt{mpfr\_remainder}.
+
+If we consider $P(n,z)$ and $Q(n,z)$ together as one single series,
+its term of index $k$
+behaves like $\Gamma(1/2+n+k)/k!/\Gamma(1/2+n-k)/(2z)^k$.
+The ratio between the
+term of index $k+1$ and that of index $k$ is about $k/(2z)$, thus starts
+to diverge when $k \approx 2z$. At that point, the $k$th term is
+$\approx e^{-2z}$, thus if $z > p/2 \log 2$, we can use the asymptotic
+expansion.
+
 \subsubsection{Bessel function $Y_n(z)$ of second kind}
 
 Like $J_n(z)$, $Y_n(z)$ is a solution of the linear differential equation:
diff --git a/jn.c b/jn.c
index 62075763c..26bdd8aad 100644
--- a/jn.c
+++ b/jn.c
@@ -26,6 +26,8 @@ MA 02110-1301, USA. */
 
 /* Relations: j(-n,z) = (-1)^n j(n,z) */
 
+static int mpfr_jn_asympt (mpfr_ptr, long, mpfr_srcptr, mp_rnd_t);
+
 int
 mpfr_j0 (mpfr_ptr res, mpfr_srcptr z, mp_rnd_t r)
 {
@@ -94,6 +96,16 @@ mpfr_jn (mpfr_ptr res, long n, mpfr_srcptr z, mp_rnd_t r)
     MPFR_FAST_COMPUTE_IF_SMALL_INPUT (res, z, -2 * MPFR_GET_EXP (z), 3,
                                       0, r, mpfr_div_2ui (res, res, 1, r));
 
+  /* we can use the asymptotic expansion as soon as |z| > p log(2)/2,
+     but to get some margin we use it for |z| > p/2 */
+  if (mpfr_cmp_ui (z, MPFR_PREC(res) / 2 + 3) > 0 ||
+      mpfr_cmp_si (z, - ((long) MPFR_PREC(res) / 2 + 3)) < 0)
+    {
+      inex = mpfr_jn_asympt (res, n, z, r);
+      if (inex != 0)
+        return inex;
+    }
+
   mpfr_init2 (y, 32);
 
   /* check underflow case: |j(n,z)| <= 1/sqrt(2 Pi n) (ze/2n)^n
@@ -188,3 +200,218 @@ mpfr_jn (mpfr_ptr res, long n, mpfr_srcptr z, mp_rnd_t r)
 
   return inex;
 }
+
+/* Implements asymptotic expansion (formula 9.2.5 from Abramowitz & Stegun).
+   Assumes z > p log(2)/2, where p is the target precision.
+   Return 0 if the expansion does not converge enough (the value 0 as inexact
+   flag should not happen for normal input).
+*/
+static int
+mpfr_jn_asympt (mpfr_ptr res, long n, mpfr_srcptr z, mp_rnd_t r)
+{
+  mpfr_t s, c, P, Q, t, iz, err_t, err_s, err_u;
+  mp_prec_t w;
+  long k;
+  int inex, stop, diverge = 0;
+  mp_exp_t err2, err;
+  MPFR_ZIV_DECL (loop);
+
+  mpfr_init (c);
+
+  w = MPFR_PREC(res) + MPFR_INT_CEIL_LOG2(MPFR_PREC(res)) + 4;
+
+  MPFR_ZIV_INIT (loop, w);
+  for (;;)
+    {
+      mpfr_set_prec (c, w);
+      mpfr_init2 (s, w);
+      mpfr_init2 (P, w);
+      mpfr_init2 (Q, w);
+      mpfr_init2 (t, w);
+      mpfr_init2 (iz, w);
+      mpfr_init2 (err_t, 31);
+      mpfr_init2 (err_s, 31);
+      mpfr_init2 (err_u, 31);
+
+      /* Approximate sin(z) and cos(z). In the following, err <= k means that
+         the approximate value y and the true value x are related by 
+         y = x * (1 + u)^k with |u| <= 2^(-w), following Higham's method. */
+      mpfr_sin_cos (s, c, z, GMP_RNDN);
+      if (MPFR_IS_NEG(z))
+        mpfr_neg (s, s, GMP_RNDN); /* compute jn(|z|), fix sign later */
+      /* The absolute error on s/c is bounded by 1/2 ulp(1/2) <= 2^(-w-1). */
+      mpfr_add (t, s, c, GMP_RNDN);
+      mpfr_sub (c, s, c, GMP_RNDN);
+      mpfr_swap (s, t);
+      /* now s approximates sin(z)+cos(z), and c approximates sin(z)-cos(z),
+         with total absolute error bounded by 2^(1-w). */
+
+      /* precompute 1/(8|z|) */
+      mpfr_si_div (iz, MPFR_IS_POS(z) ? 1 : -1, z, GMP_RNDN);   /* err <= 1 */
+      mpfr_div_2ui (iz, iz, 3, GMP_RNDN);
+
+      /* compute P and Q */
+      mpfr_set_ui (P, 1, GMP_RNDN);
+      mpfr_set_ui (Q, 0, GMP_RNDN);
+      mpfr_set_ui (t, 1, GMP_RNDN); /* current term */
+      mpfr_set_ui (err_t, 0, GMP_RNDN); /* error on t */
+      mpfr_set_ui (err_s, 0, GMP_RNDN); /* error on P and Q (sum of errors) */
+      for (k = 1, stop = 0; stop < 4; k++)
+        {
+          /* compute next term: t(k)/t(k-1) = (2n+2k-1)(2n-2k+1)/(8kz) */
+          mpfr_mul_si (t, t, 2 * (n + k) - 1, GMP_RNDN); /* err <= err_k + 1 */
+          mpfr_mul_si (t, t, 2 * (n - k) + 1, GMP_RNDN); /* err <= err_k + 2 */
+          mpfr_div_ui (t, t, k, GMP_RNDN);               /* err <= err_k + 3 */
+          mpfr_mul (t, t, iz, GMP_RNDN);                 /* err <= err_k + 5 */
+          /* the relative error on t is bounded by (1+u)^(5k)-1, which is
+             bounded by 6ku for 6ku <= 0.02: first |5 log(1+u)| <= |5.5u|
+             for |u| <= 0.15, then |exp(5.5u)-1| <= 6u for |u| <= 0.02. */
+          mpfr_mul_ui (err_t, t, 6 * k, MPFR_IS_POS(t) ? GMP_RNDU : GMP_RNDD);
+          mpfr_abs (err_t, err_t, GMP_RNDN); /* exact */
+          /* the absolute error on t is bounded by err_t * 2^(-w) */
+          mpfr_abs (err_u, t, GMP_RNDU);
+          mpfr_mul_2ui (err_u, err_u, w, GMP_RNDU); /* t * 2^w */
+          mpfr_add (err_u, err_u, err_t, GMP_RNDU); /* max|t| * 2^w */
+          if (stop >= 2)
+            {
+              /* take into account the neglected terms: t * 2^(-w) */
+              mpfr_mul_2ui (err_s, err_s, w, GMP_RNDU);
+              if (MPFR_IS_POS(t))
+                mpfr_add (err_s, err_s, t, GMP_RNDU);
+              else
+                mpfr_sub (err_s, err_s, t, GMP_RNDU);
+              mpfr_div_2ui (err_s, err_s, w, GMP_RNDU);
+              stop ++;
+            }
+          /* if k is odd, add to Q, otherwise to P */
+          else if (k & 1)
+            {
+              /* if k = 1 mod 4, add, otherwise subtract */
+              if ((k & 2) == 0)
+                mpfr_add (Q, Q, t, GMP_RNDN);
+              else
+                mpfr_sub (Q, Q, t, GMP_RNDN);
+              /* check if the next term is smaller than ulp(Q): if EXP(err_u)
+                 <= EXP(Q), since the current term is bounded by
+                 err_u * 2^(-w), it is bounded by ulp(Q) */
+              if (MPFR_EXP(err_u) <= MPFR_EXP(Q))
+                stop ++;
+              else
+                stop = 0;
+            }
+          else
+            {
+              /* if k = 0 mod 4, add, otherwise subtract */
+              if ((k & 2) == 0)
+                mpfr_add (P, P, t, GMP_RNDN);
+              else
+                mpfr_sub (P, P, t, GMP_RNDN);
+              /* check if the next term is smaller than ulp(P) */
+              if (MPFR_EXP(err_u) <= MPFR_EXP(P))
+                stop ++;
+              else
+                stop = 0;
+            }
+          mpfr_add (err_s, err_s, err_t, GMP_RNDU);
+          /* the sum of the rounding errors on P and Q is bounded by
+             err_s * 2^(-w) */
+
+          /* stop when start to diverge */
+          if (stop < 2 &&
+              ((MPFR_IS_POS(z) && mpfr_cmp_ui (z, (k + 1) / 2) < 0) ||
+               (MPFR_IS_NEG(z) && mpfr_cmp_si (z, - ((k + 1) / 2)) > 0)))
+            {
+              /* if we have to stop the series because it diverges, then
+                 increasing the precision will most probably fail, since
+                 we will stop to the same point, and thus compute a very
+                 similar approximation */
+              diverge = 1;
+              stop = 2; /* force stop */
+            }
+        }
+      /* the sum of the total errors on P and Q is bounded by err_s * 2^(-w) */
+
+      /* Now combine: the sum of the rounding errors on P and Q is bounded by
+         err_s * 2^(-w), and the absolute error on s/c is bounded by 2^(1-w) */
+      if ((n & 1) == 0) /* n even: P * (sin + cos) + Q (cos - sin) */
+        {
+          mpfr_mul (c, c, Q, GMP_RNDN); /* Q * (sin - cos) */
+          err = MPFR_EXP(c);
+          mpfr_mul (s, s, P, GMP_RNDN); /* P * (sin + cos) */
+          if (MPFR_EXP(s) > err)
+            err = MPFR_EXP(s);
+          mpfr_sub (s, s, c, GMP_RNDN);
+        }
+      else /* n odd: P * (sin - cos) + Q (cos + sin) */
+        {
+          mpfr_mul (c, c, P, GMP_RNDN); /* P * (sin - cos) */
+          err = MPFR_EXP(c);
+          mpfr_mul (s, s, Q, GMP_RNDN); /* Q * (sin + cos) */
+          if (MPFR_EXP(s) > err)
+            err = MPFR_EXP(s);
+          mpfr_add (s, s, c, GMP_RNDN);
+        }
+      if ((n & 2) != 0)
+        mpfr_neg (s, s, GMP_RNDN);
+      if (MPFR_EXP(s) > err)
+        err = MPFR_EXP(s);
+      /* the absolute error on s is bounded by P*err(s/c) + Q*err(s/c)
+         + err(P)*(s/c) + err(Q)*(s/c) + 3 * 2^(err - w - 1)
+         <= (|P|+|Q|) * 2^(1-w) + err_s * 2^(1-w) + 2^err * 2^(1-w),
+         since |c|, |old_s| <= 2. */
+      err2 = (MPFR_EXP(P) >= MPFR_EXP(Q)) ? MPFR_EXP(P) + 2 : MPFR_EXP(Q) + 2;
+      /* (|P| + |Q|) * 2^(1 - w) <= 2^(err2 - w) */
+      err = MPFR_EXP(err_s) >= err ? MPFR_EXP(err_s) + 2 : err + 2;
+      /* err_s * 2^(1-w) + 2^old_err * 2^(1-w) <= 2^err * 2^(-w) */
+      err2 = (err >= err2) ? err + 1 : err2 + 1;
+      /* now the absolute error on s is bounded by 2^(err2 - w) */
+      
+      /* multiply by sqrt(1/(Pi*z)) */
+      mpfr_const_pi (c, GMP_RNDN);     /* Pi, err <= 1 */
+      mpfr_mul (c, c, z, GMP_RNDN);    /* err <= 2 */
+      mpfr_si_div (c, MPFR_IS_POS(z) ? 1 : -1, c, GMP_RNDN); /* err <= 3 */
+      mpfr_sqrt (c, c, GMP_RNDN);      /* err<=5/2, thus the absolute error is
+                                          bounded by 3*u*|c| for |u| <= 0.25 */
+      mpfr_mul (err_t, c, s, MPFR_SIGN(c)==MPFR_SIGN(s) ? GMP_RNDU : GMP_RNDD);
+      mpfr_abs (err_t, err_t, GMP_RNDU);
+      mpfr_mul_ui (err_t, err_t, 3, GMP_RNDU);
+      /* 3*2^(-w)*|old_c|*|s| [see below] is bounded by err_t * 2^(-w) */
+      err2 += MPFR_EXP(c);
+      /* |old_c| * 2^(err2 - w) [see below] is bounded by 2^(err2-w) */
+      mpfr_mul (c, c, s, GMP_RNDN);    /* the absolute error on c is bounded by
+                                          1/2 ulp(c) + 3*2^(-w)*|old_c|*|s|
+                                          + |old_c| * 2^(err2 - w) */
+      /* compute err_t * 2^(-w) + 1/2 ulp(c) = (err_t + 2^EXP(c)) * 2^(-w) */
+      err = (MPFR_EXP(err_t) > MPFR_EXP(c)) ? MPFR_EXP(err_t) + 1 : MPFR_EXP(c) + 1;
+      /* err_t * 2^(-w) + 1/2 ulp(c) <= 2^(err - w) */
+      /* now err_t * 2^(-w) bounds 1/2 ulp(c) + 3*2^(-w)*|old_c|*|s| */
+      err = (err >= err2) ? err + 1 : err2 + 1;
+      /* the absolute error on c is bounded by 2^(err - w) */
+
+      mpfr_clear (s);
+      mpfr_clear (P);
+      mpfr_clear (Q);
+      mpfr_clear (t);
+      mpfr_clear (iz);
+      mpfr_clear (err_t);
+      mpfr_clear (err_s);
+      mpfr_clear (err_u);
+
+      err -= MPFR_EXP(c);
+      if (MPFR_LIKELY (MPFR_CAN_ROUND (c, w - err, MPFR_PREC(res), r)))
+        break;
+      if (diverge != 0)
+        {
+          mpfr_set (c, z, r); /* will force inex=0 below, which means the
+                               asymptotic expansion failed */
+          break;
+        }
+      MPFR_ZIV_NEXT (loop, w);
+    }
+  MPFR_ZIV_FREE (loop);
+
+  inex = MPFR_IS_POS(z) ? mpfr_set (res, c, r) : mpfr_neg (res, c, r);
+  mpfr_clear (c);
+
+  return inex;
+}
diff --git a/tests/data/j0 b/tests/data/j0
index 58454ece9..51d81882c 100644
--- a/tests/data/j0
+++ b/tests/data/j0
@@ -1065,3 +1065,5 @@
 53 53 n 0x1F06343D0971FBp-47 0x1F32FAADC9C90Fp-98
 53 53 n 0x1F06343D09C6A7p-47 0x112F1357417BEAp-88
 53 53 n 0x1F06343D0A11B5p-47 0x1031CA8324C806p-87
+# below are test cases not in Gonnet's testsuite
+53 53 n 0x1p1000 0x1DE62DD27F8FBDp-554
diff --git a/tests/tj0.c b/tests/tj0.c
index b7dea925d..5c820031f 100644
--- a/tests/tj0.c
+++ b/tests/tj0.c
@@ -27,6 +27,7 @@ MA 02110-1301, USA. */
 
 #define TEST_FUNCTION mpfr_j0
 #define RAND_FUNCTION(x) mpfr_random2(x, MPFR_LIMB_SIZE (x), 8)
+#define REDUCE_EMAX 262143 /* otherwise arg. reduction is too expensive */
 #include "tgeneric.c"
 
 int
diff --git a/tests/tj1.c b/tests/tj1.c
index d0b68c0be..8dd7b8da6 100644
--- a/tests/tj1.c
+++ b/tests/tj1.c
@@ -27,6 +27,7 @@ MA 02110-1301, USA. */
 
 #define TEST_FUNCTION mpfr_j1
 #define RAND_FUNCTION(x) mpfr_random2(x, MPFR_LIMB_SIZE (x), 8)
+#define REDUCE_EMAX 262143 /* otherwise arg. reduction is too expensive */
 #include "tgeneric.c"
 
 int