src/float/transcendental/cl_LF_ratseries_a.cc

   1 // eval_rational_series().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cl_LF_tran.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cln/lfloat.h"
  13 #include "cln/integer.h"
  14 #include "cln/abort.h"
  15 #include "cl_LF.h"
  16
  17 namespace cln {
  18
  19 // Subroutine.
  20 // Evaluates S = sum(N1 <= n < N2, a(n)/b(n) * (p(N1)...p(n))/(q(N1)...q(n)))
  21 // and returns P = p(N1)...p(N2-1), Q = q(N1)...q(N2-1), B = B(N1)...B(N2-1)
  22 // and T = B*Q*S (all integers). On entry N1 < N2.
  23 // P will not be computed if a NULL pointer is passed.
  24
  25 static void eval_a_series_aux (uintL N1, uintL N2,
  26                                const cl_a_series& args,
  27                                cl_I* T)
  28 {
  29         switch (N2 - N1) {
  30         case 0:
  31                 cl_abort(); break;
  32         case 1:
  33                 *T = args.av[N1];
  34                 break;
  35         case 2: {
  36                 *T = args.av[N1]
  37                    + args.av[N1+1];
  38                 break;
  39                 }
  40         case 3: {
  41                 *T = args.av[N1]
  42                    + args.av[N1+1]
  43                    + args.av[N1+2];
  44                 break;
  45                 }
  46         case 4: {
  47                 *T = args.av[N1]
  48                    + args.av[N1+1]
  49                    + args.av[N1+2]
  50                    + args.av[N1+3];
  51                 break;
  52                 }
  53         default: {
  54                 var uintL Nm = (N1+N2)/2; // midpoint
  55                 // Compute left part.
  56                 var cl_I LT;
  57                 eval_a_series_aux(N1,Nm,args,&LT);
  58                 // Compute right part.
  59                 var cl_I RT;
  60                 eval_a_series_aux(Nm,N2,args,&RT);
  61                 // Put together partial results.
  62                 // S = LS + RS, so T = LT + RT.
  63                 *T = LT + RT;
  64                 break;
  65                 }
  66         }
  67 }
  68
  69 const cl_LF eval_rational_series (uintL N, const cl_a_series& args, uintC len)
  70 {
  71         if (N==0)
  72                 return cl_I_to_LF(0,len);
  73         var cl_I T;
  74         eval_a_series_aux(0,N,args,&T);
  75         return cl_I_to_LF(T,len);
  76 }
  77 // Bit complexity (if p(n), q(n), a(n), b(n) have length O(log(n))):
  78 // O(log(N)^2*M(N)).
  79
  80 }  // namespace cln