FEE method

In mathematics, theFEE method,orfast E-function evaluation method,is the method of fast summation of series of a special form. It was constructed in 1990 byEkaterina Karatsubaand is so-named because it makes fast computations of theSiegelE-functionspossible, in particular of$e^{x}$.

A class of functions, which are "similar to the exponential function," was given the name "E-functions" byCarl Ludwig Siegel.Among these functions are suchspecial functionsas thehypergeometric function,cylinder,sphericalfunctions and so on.

Using the FEE, it is possible to prove the following theorem:

Theorem:Let$y=f(x)$be anelementarytranscendental function,that is theexponential function,or a trigonometric function,or anelementary algebraic function,or their superposition, or theirinverse,or a superposition of the inverses. Then

$s_{f}(n)=O(M(n)\log ^{2}n).\,$

Here$s_{f}(n)$is thecomplexity of computation (bit)of the function$f(x)$with accuracy up to$n$digits,$M(n)$is the complexity of multiplication of two$n$-digit integers.

The algorithms based on the method FEE include the algorithms for fast calculation of any elementarytranscendental functionfor any value of the argument, the classical constantse,$\pi,$theEuler constant$\gamma,$theCatalanand theApéry constants,such higher transcendental functions as theEuler gamma functionand its derivatives, thehypergeometric,spherical,cylinder (including theBessel)functions and some other functions for algebraicvalues of the argument and parameters, theRiemann zeta functionfor integer values of the argumentand theHurwitz zeta functionfor integer argument and algebraic values of the parameter,and also such special integrals as theintegral of probability,theFresnel integrals,theintegral exponential function,thetrigonometric integrals,and some other integralsfor 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).\,$

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'sand 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 theTaylor seriesfor

$\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},$

with the remainder terms$R_{1},$$R_{2},$which satisfy the bounds

$|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 approximationsIn 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!}},$

under the assumption that$a(j),\quad b(j)$are integers,

$|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).$

FEE calculation of the classical constante

For the evaluation of the constant$e$take$m=2^{k},\quad k\geq 1$,terms of the Taylor series for$e,$

$e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}+R_{m}.$

Here we choose$m$,requiring that for the remainder$R_{m}$the inequality$R_{m}\leq 2^{-n-1}$is fulfilled. This is the case, for example, when$m\geq {\frac {4n}{\log n}}.$Thus, we take$m=2^{k}$ such that the natural number$k$is determined by the inequalities:

$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)!}},$

in$k$steps of the following process.

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.\,$

Thus, at the first step the sum$S$is into

$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.$

At the first step${\frac {m}{2}}$integers of the form

$\ 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.

Step$i+1$($i+1\leq k$).

$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}}},$

we compute only${\frac {m}{2^{i+1}}}$integers of the form

$\ 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)!}}$

is the product of$2^{i}$integers.

Etc.

Step$k$,the last one. We compute one integer value $\ Alpha _{1}(k),$we compute, using the fast algorithm described above the value$(m-1)!,$and make one division of the integer $\ Alpha _{1}(k)$by the integer$(m-1)!,$ with accuracy up to$n$ digits. The obtained result is the sum$S,$or the constant$e$up to$n$digits. The complexity of all computations is

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

See also

• Fast algorithms
• AGM method
• Computational complexity

External links

• http:// ccas.ru/personal/karatsuba/divcen.htm
• http:// ccas.ru/personal/karatsuba/algen.htm