Fast algorithms and the FEE method

Ekatherina A. Karatsuba

Computer Centre of RAS, ul. Vavilova 40, Moscow 117967, Russia

ekar@ccas.ru

Contributed talk

Fast algorithms -- is the field of computational mathematics, which studies the algorithms for evaluation of a given function with a given accuracy, using as less as possible bit operations of computer.

The total number of bit operations, which is sufficient to compute the function $f(x)$ at the point $x=x_0$ with accuracy up to $n$ digits by means of a given algorithm, is called the complexity of computation of $f(x)$ at the point $x=x_0$ up to $n$ digits and is denoted by

$$s_f(n) = s_{f,x_0}(n).$$

We shall call fast such algorithm of computation of a function $f$ that for this algorithm

$$s_f(n)= O\left(M(n)\log^c n\right) \ ,$$

where $c$ is a constant, and $M(n)$ is the total number of bit operations, which is sufficient for computation of the product of two $n$-digit integers.

We remark, for the complexity of multiplication of two $n$-digit integers the Schönhage-Strassen bound [14], $M(n) = O(n \log n\log\log n) ,$ is valid.

It was proved in [5], [1] that based on the Newton method algorithms for the evaluation of elementary algebraic functions have the complexity upper bound $O(M(n))$ and therefore are fast.

First algorithms for fast evaluation of the constant $\pi$ and elementary transcendental functions based on the AGM-method of Gauss [6] were suggested in [4], [13], [3]. The most complete compendium of the AGM-algorithms is [2].

The FEE method was suggested and developed by author in [7]-[12]. This is the method for fast summation of the special form series. With the help of the FEE, it is possible to compute any elementary transcendental function for any argument, classical constants $e,$ $\pi,$ the Euler constant $\gamma$ and the Catalan constant, such higher transcendental functions as the Euler gamma function, hypergeometric, spherical, cylindrical and some other functions for algebraic values of the argument and parameters, the Riemann zeta function for integer argument, the Hurwitz zeta function for integer argument and algebraic values of the parameter, as well as such special integrals as the integral of probability, the Fresnel integrals, the integral exponential function and some other integrals with the complexity bound

$$O\left(M(n)\log^2 n\right) .$$

The FEE structure assumes the possibility of it's parallelizing.