# FEE method

In mathematics, the FEE method is the method of fast summation of series of a special form. It was constructed in 1990 by E. A. Karatsuba and was called FEEFast E-function Evaluation—because it makes it possible fast computations of the Siegel $E$ -functions, and in particular, $e^{x}.$ A class of functions, which are 'similar to the exponential function' was given the name 'E-functions' by Siegel. 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 $y=f(x)$ 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

$s_{f}(n)=O(M(n)\log ^{2}n).\,$ 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, $\pi ,$ the Euler constant $\gamma ,$ the Catalan and the Apéry constants, such higher transcendental functions as the Euler gamma function and its derivatives, the hypergeometric, spherical, cylinder (including the Bessel) functions and some other functions for algebraic values of the argument and parameters, the Riemann zeta function for integer values of the argument and the Hurwitz zeta function for integer argument and algebraic values of the parameter, and also such special integrals as the integral of probability, the Fresnel integrals, the integral exponential function, the trigonometric integrals, and some other integrals for algebraic values of the argument with the complexity bound which is close to the optimal one, namely

$s_{f}(n)=O(M(n)\log ^{2}n).\,$ At present,Template:When only the FEE makes it possible to calculate fast the values of the functions from the class of higher transcendental functions, certain special integrals of mathematical physics and such classical constants as Euler's, Catalan's 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 $\pi ,$ one can use the Euler formula ${\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},$ and apply the FEE to sum the Taylor series for

$\arctan {\frac {1}{2}}={\frac {1}{1\cdot 2}}-{\frac {1}{3\cdot 2^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},$ $\arctan {\frac {1}{3}}={\frac {1}{1\cdot 3}}-{\frac {1}{3\cdot 3^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},$ $|R_{1}|\leq {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};$ $|R_{2}|\leq {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};$ and for

$r=n,\,$ $4(|R_{1}|+|R_{2}|)\ <\ 2^{-n}.$ To calculate $\pi$ by the FEE it is possible to use also other approximations In all cases the complexity is

$s_{\pi }=O(M(n)\log ^{2}n).\,$ To compute the Euler constant gamma with accuracy up to $n$ digits, it is necessary to sum by the FEE two series. Namely, for

$m=6n,\quad k=n,\quad k\geq 1,\,$ $\gamma =-\log n\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!}}+\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!(r+1)}}+O(2^{-n}).$ The complexity is

$s_{\gamma }=O(M(n)\log ^{2}n).\,$ To evaluate fast the constant $\gamma$ it is possible to apply the FEE to other approximations.

## FEE-computation of certain power series

By the FEE the two following series are calculated fast:

$f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},$ $f_{2}=f_{2}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}{\frac {z^{j}}{j!}},$ $|a(j)|+|b(j)|\leq (Cj)^{K};\quad |z|\ <\ 1;\quad K$ and $C$ are constants, and $z$ is an algebraic number. The complexity of the evaluation of the series is

$s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),\,$ $s_{f_{2}}(n)=O\left(M(n)\log n\right).$ ## The FEE details on the example of fast calculation of the classical constant e

$e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}+R_{m}.$ $2^{k}\geq {\frac {4n}{\log n}}>2^{k-1}.$ We calculate the sum

$S=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}=\sum _{j=0}^{m-1}{\frac {1}{(m-1-j)!}},$ Step 1. Combining in $S$ the summands sequentially in pairs we carry out of the brackets the "obvious" common factor and obtain

{\begin{aligned}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{aligned}} We shall compute only integer values of the expressions in the parentheses, that is the values

$m,m-2,m-4,\dots .\,$ $S=S(1)=\sum _{j=0}^{m_{1}-1}{\frac {1}{(m-1-2j)!}}\alpha _{m_{1}-j}(1),$ $m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.$ $\alpha _{m_{1}-j}(1)=m-2j,\quad j=0,1,\dots ,m_{1}-1,$ are calculated. After that we act in a similar way: combining on each step the summands of the sum $S$ 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 $i$ steps of this process are completed.

$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),$ $m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},$ $\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)!}},$ $j=0,1,\dots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geq i+1.$ Here

${\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}}$ Etc.

$O\left(M(m)\log ^{2}m\right)=O\left(M(n)\log n\right).\,$ 