FEE method (original) (raw)

From Wikipedia, the free encyclopedia

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[1][2] and is so-named because it makes fast computations of the Siegel _E_-functions possible, in particular of e x {\displaystyle 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 ) {\displaystyle 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 ) . {\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).\,}

Here s f ( n ) {\displaystyle s_{f}(n)} is the complexity of computation (bit) of the function f ( x ) {\displaystyle f(x)} with accuracy up to n {\displaystyle n} digits, M ( n ) {\displaystyle M(n)} is the complexity of multiplication of two n {\displaystyle n} -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, π , {\displaystyle \pi ,} the Euler constant γ , {\displaystyle \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, namely

s f ( n ) = O ( M ( n ) log 2 ⁡ n ) . {\displaystyle 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,[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

[edit]

For fast evaluation of the constant π , {\displaystyle \pi ,} one can use the Euler formula π 4 = arctan ⁡ 1 2 + arctan ⁡ 1 3 , {\displaystyle {\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},} and apply the FEE to sum the Taylor series for

arctan ⁡ 1 2 = 1 1 ⋅ 2 − 1 3 ⋅ 2 3 + ⋯ + ( − 1 ) r − 1 ( 2 r − 1 ) 2 2 r − 1 + R 1 , {\displaystyle \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 ⁡ 1 3 = 1 1 ⋅ 3 − 1 3 ⋅ 3 3 + ⋯ + ( − 1 ) r − 1 ( 2 r − 1 ) 3 2 r − 1 + R 2 , {\displaystyle \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 , {\displaystyle R_{1},} R 2 , {\displaystyle R_{2},} which satisfy the bounds

| R 1 | ≤ 4 5 1 2 r + 1 1 2 2 r + 1 ; {\displaystyle |R_{1}|\leq {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};}

| R 2 | ≤ 9 10 1 2 r + 1 1 3 2 r + 1 ; {\displaystyle |R_{2}|\leq {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};}

and for

r = n , {\displaystyle r=n,\,}

4 ( | R 1 | + | R 2 | ) < 2 − n . {\displaystyle 4(|R_{1}|+|R_{2}|)\ <\ 2^{-n}.}

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

s π = O ( M ( n ) log 2 ⁡ n ) . {\displaystyle s_{\pi }=O(M(n)\log ^{2}n).\,}

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

m = 6 n , k = n , k ≥ 1 , {\displaystyle m=6n,\quad k=n,\quad k\geq 1,\,}

γ = − log ⁡ n ∑ r = 0 12 n ( − 1 ) r n r + 1 ( r + 1 ) ! + ∑ r = 0 12 n ( − 1 ) r n r + 1 ( r + 1 ) ! ( r + 1 ) + O ( 2 − n ) . {\displaystyle \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 γ = O ( M ( n ) log 2 ⁡ n ) . {\displaystyle s_{\gamma }=O(M(n)\log ^{2}n).\,}

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

FEE computation of certain power series

[edit]

By the FEE the two following series are calculated fast:

f 1 = f 1 ( z ) = ∑ j = 0 ∞ a ( j ) b ( j ) z j , {\displaystyle f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},}

f 2 = f 2 ( z ) = ∑ j = 0 ∞ a ( j ) b ( j ) z j j ! , {\displaystyle f_{2}=f_{2}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}{\frac {z^{j}}{j!}},}

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

| a ( j ) | + | b ( j ) | ≤ ( C j ) K ; | z | < 1 ; K {\displaystyle |a(j)|+|b(j)|\leq (Cj)^{K};\quad |z|\ <\ 1;\quad K}

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

s f 1 ( n ) = O ( M ( n ) log 2 ⁡ n ) , {\displaystyle s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),\,}

s f 2 ( n ) = O ( M ( n ) log ⁡ n ) . {\displaystyle s_{f_{2}}(n)=O\left(M(n)\log n\right).}

FEE calculation of the classical constant e

[edit]

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

e = 1 + 1 1 ! + 1 2 ! + ⋯ + 1 ( m − 1 ) ! + R m . {\displaystyle e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}+R_{m}.}

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

2 k ≥ 4 n log ⁡ n > 2 k − 1 . {\displaystyle 2^{k}\geq {\frac {4n}{\log n}}>2^{k-1}.}

We calculate the sum

S = 1 + 1 1 ! + 1 2 ! + ⋯ + 1 ( m − 1 ) ! = ∑ j = 0 m − 1 1 ( m − 1 − j ) ! , {\displaystyle 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 {\displaystyle k} steps of the following process.

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

S = ( 1 ( m − 1 ) ! + 1 ( m − 2 ) ! ) + ( 1 ( m − 3 ) ! + 1 ( m − 4 ) ! ) + ⋯ = 1 ( m − 1 ) ! ( 1 + m − 1 ) + 1 ( m − 3 ) ! ( 1 + m − 3 ) + ⋯ . {\displaystyle {\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 , … . {\displaystyle m,m-2,m-4,\dots .\,}

Thus, at the first step the sum S {\displaystyle S} is into

S = S ( 1 ) = ∑ j = 0 m 1 − 1 1 ( m − 1 − 2 j ) ! α m 1 − j ( 1 ) , {\displaystyle S=S(1)=\sum _{j=0}^{m_{1}-1}{\frac {1}{(m-1-2j)!}}\alpha _{m_{1}-j}(1),}

m 1 = m 2 , m = 2 k , k ≥ 1. {\displaystyle m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.}

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

α m 1 − j ( 1 ) = m − 2 j , j = 0 , 1 , … , m 1 − 1 , {\displaystyle \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 {\displaystyle 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 {\displaystyle i} steps of this process are completed.

Step i + 1 {\displaystyle i+1} ( i + 1 ≤ k {\displaystyle i+1\leq k} ).

S = S ( i + 1 ) = ∑ j = 0 m i + 1 − 1 1 ( m − 1 − 2 i + 1 j ) ! α m i + 1 − j ( i + 1 ) , {\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),}

m i + 1 = m i 2 = m 2 i + 1 , {\displaystyle m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},}

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

α m i + 1 − j ( i + 1 ) = α m i − 2 j ( i ) + α m i − ( 2 j + 1 ) ( i ) ( m − 1 − 2 i + 1 j ) ! ( m − 1 − 2 i − 2 i + 1 j ) ! , {\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)!}},}

j = 0 , 1 , … , m i + 1 − 1 , m = 2 k , k ≥ i + 1. {\displaystyle j=0,1,\dots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geq i+1.}

Here

( m − 1 − 2 i + 1 j ) ! ( m − 1 − 2 i − 2 i + 1 j ) ! {\displaystyle {\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}}}

is the product of 2 i {\displaystyle 2^{i}} integers.

Etc.

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

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

• Fast algorithms
• AGM method
• Computational complexity

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 ζ ( 3 ) {\displaystyle \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 ζ ( s ) {\displaystyle \zeta (s)} for integer values of argument s {\displaystyle 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 {\displaystyle 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)\zeta(3)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).

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