FEE method

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 E-functions possible, in particular of [math]\displaystyle{ e^x }[/math]. 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 [math]\displaystyle{ 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]\displaystyle{ s_f(n) = O(M(n)\log^2n). \, }[/math]

Here [math]\displaystyle{ s_f(n) }[/math] is the complexity of computation (bit) of the function [math]\displaystyle{ f(x) }[/math] with accuracy up to [math]\displaystyle{ n }[/math] digits, [math]\displaystyle{ M(n) }[/math] is the complexity of multiplication of two [math]\displaystyle{ 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]\displaystyle{ \pi, }[/math] the Euler constant [math]\displaystyle{ \gamma, }[/math] 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 for algebraic 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, namely

[math]\displaystyle{ s_{f}(n)= O(M(n)\log^2 n). \, }[/math]

At present,[when?] only 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.

## Contents

* 1 FEE computation of classical constants
* 2 FEE computation of certain power series
* 3 FEE calculation of the classical constant e
* 4 See also
* 5 References
* 6 External links

## FEE computation of classical constants

For fast evaluation of the constant [math]\displaystyle{ \pi, }[/math] one can use the Euler formula [math]\displaystyle{ \frac{\pi}{4} = \arctan \frac12 + \arctan \frac13, }[/math] and apply the FEE to sum the Taylor series for

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ R_1, }[/math] [math]\displaystyle{ R_2, }[/math] which satisfy the bounds

[math]\displaystyle{ |R_1| \leq \frac45\frac{1}{2r+1}\frac{1}{2^{2r+1}}; }[/math]

[math]\displaystyle{ |R_2| \leq \frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}}; }[/math]

and for

[math]\displaystyle{ r = n,\, }[/math]

[math]\displaystyle{ 4(|R_1|+|R_2|) \ \lt \ 2^{-n}. }[/math]

To calculate [math]\displaystyle{ \pi }[/math] by the FEE it is possible to use also other approximations[13] In all cases the complexity is

[math]\displaystyle{ s_\pi = O(M(n)\log^2 n). \, }[/math]

To compute the Euler constant gamma with accuracy up to [math]\displaystyle{ n }[/math] digits, it is necessary to sum by the FEE two series. Namely, for

[math]\displaystyle{ m=6n, \quad k = n, \quad k \geq 1, \, }[/math]

[math]\displaystyle{ \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]\displaystyle{ s_\gamma = O(M(n)\log^2 n). \, }[/math]

To evaluate fast the constant [math]\displaystyle{ \gamma }[/math] it is possible to apply the FEE to other approximations.[14]

## FEE computation of certain power series

By the FEE the two following series are calculated fast:

[math]\displaystyle{ f_1 = f_1(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}z^j , }[/math]

[math]\displaystyle{ f_2 = f_2(z) = \sum_{j=0}^{\infty}\frac{a(j)}{b(j)}\frac{z^j}{j!} , }[/math]

under the assumption that [math]\displaystyle{ a(j) , \quad b(j) }[/math] are integers,

[math]\displaystyle{ |a(j)|+|b(j)| \leq (Cj)^K; \quad |z| \ \lt \ 1; \quad K }[/math]

and [math]\displaystyle{ C }[/math] are constants, and [math]\displaystyle{ z }[/math] is an algebraic number. The complexity of the evaluation of the series is

[math]\displaystyle{ s_{f_1}(n) = O\left(M(n)\log^2n \right), \, }[/math]

[math]\displaystyle{ 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]\displaystyle{ e }[/math] take [math]\displaystyle{ m = 2^k, \quad k \geq 1 }[/math], terms of the Taylor series for [math]\displaystyle{ e, }[/math]

[math]\displaystyle{ e = 1 + \frac{1}{1!} + \frac{1}{2!} + \cdots + \frac{1}{(m-1)!} + R_m. }[/math]

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

[math]\displaystyle{ 2^k \geq \frac{4n}{\log n} \gt 2^{k-1}. }[/math]

We calculate the sum

[math]\displaystyle{ 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]\displaystyle{ k }[/math] steps of the following process.

Step 1. Combining in [math]\displaystyle{ S }[/math] the summands sequentially in pairs we carry out of the brackets the "obvious" common factor and obtain

[math]\displaystyle{ \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]\displaystyle{ m , m-2 , m-4 , \dots . \, }[/math]

Thus, at the first step the sum [math]\displaystyle{ S }[/math] is into

[math]\displaystyle{ S = S(1) = \sum_{j=0}^{m_1-1}\frac{1}{(m-1-2j)!}\alpha_{m_1-j}(1) , }[/math]

[math]\displaystyle{ m_1 = \frac m2 , m = 2^k , k \geq 1 . }[/math]

At the first step [math]\displaystyle{ \frac m2 }[/math] integers of the form

[math]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ i }[/math] steps of this process are completed.

Step [math]\displaystyle{ i+1 }[/math] ([math]\displaystyle{ i+1 \leq k }[/math]).

[math]\displaystyle{ 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]\displaystyle{ m_{i+1} = \frac{m_i}{2} = \frac{m}{2^{i+1}} , }[/math]

we compute only [math]\displaystyle{ \frac{m}{2^{i+1}} }[/math] integers of the form

[math]\displaystyle{ \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]\displaystyle{ j = 0 , 1 , \dots , \quad m_{i+1} - 1 , \quad m = 2^k , \quad k \geq i+1 . }[/math]

Here

[math]\displaystyle{ \frac{(m-1-2^{i+1}j)!}{(m-1-2^i-2^{i+1}j)!} }[/math]

is the product of [math]\displaystyle{ 2^i }[/math] integers.

Etc.

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

[math]\displaystyle{ 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

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 [math]\displaystyle{ \zeta(3) }[/math], 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 [math]\displaystyle{ \zeta(s) }[/math] for integer values of argument [math]\displaystyle{ s }[/math]. 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 [math]\displaystyle{ L }[/math]-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's constant. Math. Comp., Vol. 34 (1980).

## External links

* http://www.ccas.ru/personal/karatsuba/divcen.htm
* http://www.ccas.ru/personal/karatsuba/algen.htm

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/FEE method. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=FEE_method&oldid=3369619"