FEE method explained

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^{[1] [2]} and is so-named because it makes fast computations of the Siegel -functions possible, in particular of

e ^{x} .

A class of functions, which are "similar to the exponential function," was given the name "E-functions" by Carl Ludwig Siegel.^[3] 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. Thens _{f(n)} = O(M(n) log ^{2n).}

Here

s _{f(n)} is the complexity 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.\gamma, the Catalan and the Apéry constants,^[4] such higher transcendental functions as the Euler gamma function and its derivatives, the hypergeometric,^[5] spherical, cylinder (including the Bessel)^[6] functions and some other functions foralgebraic values of the argument and parameters, the Riemann zeta function for integer values of the argument^{[7] [8]} and the Hurwitz zeta function for integer argument and algebraic values of the parameter,^[9] and also such special integrals as the integral of probability, the Fresnel integrals, the integral exponential function, the trigonometric integrals, and some other integrals^[10] for algebraic values of the argument with the complexity bound which is close to the optimal one, namelys _{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,^[11] certain special integrals of mathematical physics and such classical constants as Euler's, Catalan's^[12] 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 theconstant

\pi, one can use the Euler formula(\pi)/(4) = \arctan (12)/(+) \arctan (13 ,)/() and apply the FEE to sum the Taylor series for\arctan (12)/(=) (1)/(1 ⋅ 2) - (1)/(3 ⋅ 2 ^{3}) + … + (( -1 ) ^{r-1})/(( 2 r -1 ) 2 ^{2r-1}) + R _{1} , \arctan (13)/(=) (1)/(1 ⋅ 3) - (1)/(3 ⋅ 3 ^{3}) + … + (( -1 ) ^{r-1})/(( 2 r -1 ) 3 ^{2r-1}) + R _{2} ,

with the remainder terms

R _{1,} R _{2,} which satisfy the bounds|R _{1|} \leq (45 (1)/(2 r +1))/((1)/(2 ^{2r+1})) ; |R _{2|} \leq (9)/(10) (1)/(2 r +1) (1)/(3 ^{2r+1}) ;

and for

r = n, 4 (|R _{1|+|R} _{2|)} < 2 ^{-n} .

To calculate

\pi by theFEE it is possible to use also other approximations^[13] In all cases the complexity iss _{\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, form =6 n, k = n, k \geq 1 , \gamma = - log n \sum ^{12 n} _{r =0} (( -1 ) ^{rn} ^{r+1})/((r +1 )!) + \sum ^{12 n} _{r =0} (( -1 ) ^{rn} ^{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 theFEE to other approximations.^[14]

FEE computation of certain power series

By the FEE the two following series are calculated fast:

f _{1} = f _{1(z)} = \sum ^{inf ty} _{j =0} (a(j))/(b(j)) z ^{j} , f _{2} = f _{2(z)} = \sum ^{inf ty} _{j =0} (a(j))/(b(j)) (z ^{j})/(j!) ,

under the assumption that

a(j) , b(j) areintegers,|a(j)| + |b(j)| \leq (Cj) ^{K;} |z| < 1 ; K

and

C are constants, and z is an algebraic number. The complexity of the evaluation of the series iss _{f _{1}} (n) = O\left(M(n) log ^{2n} \right), s _{f _{2}} (n) = O\left(M(n) log n \right).

FEE calculation of the classical constant e

For the evaluation of the constant

e take m = 2 ^{k,} k \geq 1 , terms of the Taylor series for e, e = 1 + (1)/(1 !) + (1)/(2 !) + … + (1)/((m -1 )!) + R _{m.}

Here we choose

m , requiring that for the remainder R _{m} theinequality R _{m} \leq 2 ^{-n-1} is fulfilled. This is the case, forexample, when m\geq (4 n)/(log n) . Thus, we take m =2 ^{k} such that the natural number k is determined by theinequalities:2 ^{k} \geq (4 n)/(log n) > 2 ^{k-1} .

We calculate the sum

S = 1 + (1)/(1 !) + (1)/(2 !) + … + (1)/((m -1 )!) = \sum ^{m -1} _{j =0} (1)/((m -1- j)!) ,

in

k steps of the following process.

Step 1. Combining in

S the summands sequentially in pairs wecarry out of the brackets the "obvious" common factor and obtain\begin{align} S & = \left( (1)/((m -1 )!) + (1)/((m -2 )!) \right) + \left( (1)/((m -3 )!) + (1)/((m -4 )!) \right) + … \\ & = (1)/((m -1 )!) ( 1+ m -1 ) + (1)/((m -3 )!) ( 1+ m -3 ) + … . \end{align}

We shall compute only integer values of the expressions in theparentheses, that is the values

m , m -2 , m -4 , ... .

Thus, at the first step the sum

S is intoS = S( 1 ) = \sum ^{m _{1-1}} _{j =0} (1)/((m -1-2 j)!) \alpha _{m _{1-j}} ( 1 ) , m _{1} = (m 2)/(,) m = 2 ^{k} , k \geq 1 .

At the first step

(m 2)/() integers of the form\alpha _{m _{1-j}} ( 1 ) = m -2 j , j = 0 , 1 , ... , m _{1} - 1 ,

are calculated. After that we act in a similar way: combining oneach step the summands of the sum

S sequentially in pairs, wetake out of the brackets the 'obvious' common factor and computeonly the integer values of the expressions in the brackets. Assumethat the first i steps of this process are completed.

Step

i +1 (i +1 \leq k ).S = S(i +1 ) = \sum ^{m _{i+1} -1} _{j =0} (1)/((m -1-2 ^{i+1} j)!) \alpha _{m _{i+1} - j} (i +1 ) , m _{i+1} = (m _{i})/(2) = (m)/(2 ^{i+1}) ,

we compute only

(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) ((m -1-2 ^{i+1} j)!)/((m -1-2 ^{i-2} ^{i+1} j)!) , j = 0 , 1 , ... , m _{i+1} - 1 , m = 2 ^{k} , k \geq i +1 .

Here

((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 describedabove 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 upto n digits. The complexity of all computations isO\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://www.ccas.ru/personal/karatsuba/divcen.htm
• http://www.ccas.ru/personal/karatsuba/algen.htm

Notes and References

1. E. A. Karatsuba, Fast evaluations of transcendental functions. Probl. Peredachi Informat., Vol. 27, No. 4, (1991)
2. 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).
3. C. L. Siegel,Transcendental numbers. Princeton University Press, Princeton (1949).
4. Karatsuba E. A., Fast evaluation of \zeta( 3 ) , Probl. Peredachi Informat., Vol. 29, No. 1 (1993)
5. 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)
6. Catherine A. Karatsuba, Fast evaluation of Bessel functions. Integral Transforms and Special Functions, Vol. 1, No. 4 (1993)
7. E. A. Karatsuba, Fast Evaluation of Riemann zeta-function \zeta(s) for integer values of argument s . Probl. Peredachi Informat., Vol. 31, No. 4 (1995).
8. 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).
9. E. A. Karatsuba, Fast evaluation of Hurwitz zeta function and Dirichlet L -series, Problem. Peredachi Informat., Vol. 34, No. 4, pp. 342–353, (1998).
10. 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).
11. E. Bach, The complexity of number-theoretic constants. Info. Proc. Letters, No. 62 (1997).
12. 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).
13. D. H. Bailey, P. B. Borwein and S. Plouffe,On the rapid computation of various polylogarithmic constants. Math.Comp., Vol. 66 (1997).
14. R. P. Brent and E. M. McMillan,Some new algorithms for high-precision computation of Euler'sconstant. Math. Comp., Vol. 34 (1980).