{{Short description|Fast summation method in mathematics}} In mathematics, the '''FEE method''', or '''fast E-function evaluation method''', is the method of fast summation of series of a special form. It was constructed in 1990 by Ekaterina Karatsuba<ref>E. A. Karatsuba, Fast evaluations of transcendental functions. Probl. Peredachi Informat., Vol. 27, No. 4, (1991)</ref><ref>D. W. Lozier and F. W. J. Olver, Numerical Evaluation of Special Functions. Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, W. Gautschi, eds., Proc. Sympos. Applied Mathematics, AMS, Vol. 48 (1994).</ref> and is so-named because it makes fast computations of the Siegel {{math|1=''E''}}-functions possible, in particular of <math>e^x</math>.
A class of functions, which are "similar to the exponential function," was given the name "E-functions" by Carl Ludwig Siegel.<ref>C. L. Siegel, ''Transcendental numbers''. Princeton University Press, Princeton (1949).</ref> Among these functions are such special functions as the hypergeometric function, cylinder, spherical functions and so on.
Using the FEE, it is possible to prove the following theorem:
'''Theorem''': Let <math>y=f(x)</math> be an '''elementary transcendental function''', that is the exponential function, or a trigonometric function, or an elementary algebraic function, or their superposition, or their inverse, or a superposition of the inverses. Then
<math> s_f(n) = O(M(n)\log^2n). \, </math>
Here <math>s_f(n)</math> is the complexity of computation (bit) of the function <math>f(x)</math> with accuracy up to <math>n</math> digits, <math>M(n)</math> is the complexity of multiplication of two <math>n</math>-digit integers.
The algorithms based on the method FEE include the algorithms for fast calculation of any elementary transcendental function for any value of the argument, the classical constants e, <math>\pi,</math> the Euler constant <math>\gamma,</math> the Catalan and the Apéry constants,<ref>Karatsuba E. A., Fast evaluation of <math>\zeta(3)</math>, Probl. Peredachi Informat., Vol. 29, No. 1 (1993)</ref> such higher transcendental functions as the Euler gamma function and its derivatives, the hypergeometric,<ref>Ekatharine A. Karatsuba, Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT'97), N. Papamichael, St. Ruscheweyh and E. B. Saff, eds., World Sc. Pub. (1999)</ref> spherical, cylinder (including the Bessel)<ref>Catherine A. Karatsuba, Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol. 1, No. 4 (1993)</ref> functions and some other functions for algebraic values of the argument and parameters, the Riemann zeta function for integer values of the argument<ref>E. A. Karatsuba, Fast Evaluation of Riemann zeta-function <math>\zeta(s)</math> for integer values of argument <math>s</math>. Probl. Peredachi Informat., Vol. 31, No. 4 (1995).</ref><ref>J. M. Borwein, D. M. Bradley and R. E. Crandall, Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., Vol. 121, No. 1–2 (2000).</ref> and the Hurwitz zeta function for integer argument and algebraic values of the parameter,<ref>E. A. Karatsuba, Fast evaluation of Hurwitz zeta function and Dirichlet <math>L</math>-series, Problem. Peredachi Informat., Vol. 34, No. 4, pp. 342–353, (1998).</ref> and also such special integrals as the integral of probability, the Fresnel integrals, the integral exponential function, the trigonometric integrals, and some other integrals<ref>E. A. Karatsuba, Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W. Kramer, J. W. von Gudenberg, eds.(2001).</ref> for algebraic values of the argument with the complexity bound which is close to the optimal one, namely
<math> s_{f}(n)= O(M(n)\log^2 n). \, </math>
The FEE makes it possible to calculate fast the values of the functions from the class of higher transcendental functions,<ref>E. Bach, The complexity of number-theoretic constants. Info. Proc. Letters, No. 62 (1997).</ref> certain special integrals of mathematical physics and such classical constants as Euler's, Catalan's<ref>E. A. Karatsuba, Fast computation of $\zeta(3)$ and of some special integrals, using the polylogarithms, the Ramanujan formula and its generalization. J. of Numerical Mathematics BIT, Vol. 41, No. 4 (2001).</ref> and Apéry's constants. An additional advantage of the method FEE is the possibility of parallelizing the algorithms based on the FEE.
== FEE computation of classical constants ==
For fast evaluation of the constant <math>\pi,</math> one can use the Machin-like formula <math>\frac{\pi}{4} = \arctan \frac12 + \arctan \frac13,</math> and apply the FEE to sum the Taylor series for
:<math> \arctan \frac12 = \frac{1}{1\cdot 2} - \frac{1}{3\cdot 2^3}+ \cdots + \frac{(-1)^{r-1}}{(2r-1)2^{2r-1}} + R_1 , </math>
:<math> \arctan \frac13 = \frac{1}{1\cdot 3} - \frac{1}{3\cdot 3^3}+ \cdots + \frac{(-1)^{r-1}}{(2r-1)3^{2r-1}} + R_2 , </math>
with the remainder terms <math>R_1,</math> <math>R_2,</math> which satisfy the bounds
:<math>|R_1| \leq \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}}; </math>
:<math>|R_2| \leq \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};</math>
and for
:<math>r = n,\,</math>
:<math>4(|R_1|+|R_2|) \ < \ 2^{-n}.</math>
To calculate <math>\pi</math> by the FEE it is possible to use also other approximations<ref>D. H. Bailey, P. B. Borwein and S. Plouffe, On the rapid computation of various polylogarithmic constants. Math. Comp., Vol. 66 (1997).</ref> In all cases the complexity is
:<math>s_\pi = O(M(n)\log^2 n). \,</math>
To compute the Euler constant gamma with accuracy up to <math>n</math> digits, it is necessary to sum by the FEE two series. Namely, for
:<math>m=6n, \quad k = n, \quad k \geq 1, \, </math>
:<math> \gamma = - \log n \sum_{r=0}^{12n} \frac{(-1)^rn^{r+1}}{(r+1)!} + \sum_{r=0}^{12n} \frac{(-1)^rn^{r+1}}{(r+1)!(r+1)} + O(2^{-n}) . </math>
The complexity is
:<math>s_\gamma = O(M(n)\log^2 n). \, </math>
To evaluate fast the constant <math>\gamma</math> it is possible to apply the FEE to other approximations.<ref>R. P. Brent and E. M. McMillan, Some new algorithms for high-precision computation of Euler's constant. Math. Comp., Vol. 34 (1980).</ref>
== FEE computation of certain power series ==
By the FEE the two following series are calculated fast:
:<math> f_1 = f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j , </math>
:<math>f_2 = f_2(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!} , </math>
under the assumption that <math>a(j) , \quad b(j)</math> are integers,
:<math>|a(j)|+|b(j)| \leq (Cj)^K; \quad |z| \ < \ 1; \quad K</math>
and <math>C</math> are constants, and <math>z</math> is an algebraic number. The complexity of the evaluation of the series is
:<math> s_{f_1}(n) = O\left(M(n)\log^2n \right), \, </math>
:<math> s_{f_2}(n)= O\left(M(n)\log n \right). </math>
== FEE calculation of the classical constant ''e'' ==
For the evaluation of the constant <math>e</math> take <math>m = 2^k, \quad k \geq 1</math>, terms of the Taylor series for <math>e,</math>
:<math> e = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} + R_m. </math>
Here we choose <math>m</math>, requiring that for the remainder <math>R_m</math> the inequality <math>R_m \leq 2^{-n-1}</math> is fulfilled. This is the case, for example, when <math>m\geq \frac{4n}{\log n}.</math> Thus, we take <math>m=2^k</math> such that the natural number <math>k</math> is determined by the inequalities:
:<math> 2^k \geq \frac{4n}{\log n} > 2^{k-1}. </math>
We calculate the sum
:<math> S = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} = \sum_{j=0}^{m-1}\frac{1}{(m-1-j)!} , </math>
in <math>k</math> steps of the following process.
Step 1. Combining in <math>S</math> the summands sequentially in pairs we carry out of the brackets the "obvious" common factor and obtain
:<math> \begin{align} S & = \left(\frac{1}{(m-1)!} + \frac{1}{(m-2)!}\right) + \left(\frac{1}{(m-3)!} + \frac{1}{(m-4)!}\right) + \cdots \\ & = \frac{1}{(m-1)!}(1+m-1) + \frac{1}{(m-3)!}(1+m-3) + \cdots . \end{align} </math>
We shall compute only integer values of the expressions in the parentheses, that is the values
:<math> m , m-2 , m-4 , \dots . \, </math>
Thus, at the first step the sum <math>S</math> is into
:<math> S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1) , </math>
:<math> m_1 = \frac m2 , m = 2^k , k \geq 1 .</math>
At the first step <math>\frac m2</math> integers of the form
:<math> \alpha_{m_1-j}(1) = m-2j , \quad j = 0 , 1 , \dots , m_1 - 1 , </math>
are calculated. After that we act in a similar way: combining on each step the summands of the sum <math>S</math> sequentially in pairs, we take out of the brackets the 'obvious' common factor and compute only the integer values of the expressions in the brackets. Assume that the first <math>i</math> steps of this process are completed.
Step <math>i+1</math> (<math>i+1 \leq k</math>).
:<math> S = S(i+1) = \sum_{j=0}^{m_{i+1}-1}\frac{1}{(m-1-2^{i+1}j)!} \alpha_{m_{i+1}-j}(i+1) ,</math>
:<math> m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}} , </math>
we compute only <math>\frac{m}{2^{i+1}}</math> integers of the form
:<math> \alpha_{m_{i+1}-j}(i+1) = \alpha_{m_i-2j}(i) + \alpha_{m_i-(2j+1)}(i)\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!} ,</math>
:<math>j = 0 , 1 , \dots , \quad m_{i+1} - 1 , \quad m = 2^k , \quad k \geq i+1 .</math>
Here
:<math>\frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!}</math>
is the product of <math>2^i</math> integers.
Etc.
Step <math>k</math>, the last one. We compute one integer value <math>\alpha_1(k),</math> we compute, using the fast algorithm described above the value <math>(m-1)!,</math> and make one division of the integer <math>\alpha_1(k)</math> by the integer <math>(m-1)!,</math> with accuracy up to <math>n</math> digits. The obtained result is the sum <math>S,</math> or the constant <math>e</math> up to <math>n</math> digits. The complexity of all computations is
:<math> O\left(M(m)\log^2 m\right) = O\left(M(n)\log n\right). \, </math>
==See also== *Fast algorithms *AGM method *Computational complexity
==References== {{reflist}}
==External links== * http://www.ccas.ru/personal/karatsuba/divcen.htm * http://www.ccas.ru/personal/karatsuba/algen.htm
{{DEFAULTSORT:Fee Method}} Category:Numerical analysis Category:Computer arithmetic algorithms Category:Pi algorithms