The field of computational mathematics, which is called **Fast Algorithms,** was born in 1960. By an algorithm, not formalizing this concept, we mean a rule or a way of computation.

We assume that numbers are written in the binary form, the signs of which **0** and **1** are called bits.

**Def. 1.** *Writing down of one of the symbols* **0,
1, +, –, (, ),** * putting together, subtraction and multiplication of two bits is called an elementary operation or a bit operation.*

Fast Algorithms is the field of computational mathematics that studies algorithms of evaluation of a given function with a given accuracy, using as few bit operations as possible. Thus the algorithms, which, can be called fast ones, are real algorithms. Realizing such algorithms in software (and sometimes in hardware) it is possible to increase essentially the computer's efficiency, and sometimes to solve problems of the size that didn't permit a solution by means of ordinary methods of computation. The question of the size of a problem, which can be solved in a certain time with the help of a given computer, leads us to the concept of complexity of computation.

In what follows, unless otherwise specified, the complexity of calculations means the bit complexity.

The problem of complexity of computation was first formulated by A. N. Kolmogorov (1956) [37], [38], who emphasized at the same time, that ‘... the series of my works on information theory was created in the 50s and 60s under a strong influence of publications by Norbert Wiener and Claude Shannon ...’

Before we introduce the concept of complexity of computation, we define what it means to evaluate a function at a given point. Consider the simplest case: let **y = f(x)** be a real function of a real argument ** x, a ≤ x ≤ b**, and assume that **f(x)** satisfies on **(a,b)** the Lipschitz condition of order **α, 0 < α <1,** that is for **x _{1}, x_{2}** ∊

**|f(x _{1}) – f(x_{2})| ≤ |x_{1} – x_{2}|^{α}.**

Let **n** be a natural number.

**Def. 2.** *To compute the function* **y = f(x)** *at the point*
**x = x _{0}** ∊

**|f(x _{0}) – A| ≤ 2^{–n}.**

**Def. 3.** *The total number of bit operations sufficient to compute the function* **f(x)** *at the point* **x = x _{0}**

This function is denoted by

It is clear that **S _{f}** depends also on the algorithm of calculation and for different algorithms will be different. The complexity of a computation is directly related to the time that the computer needs to perform this computation. For this reason, the complexity is often treated as a ‘time’ function

The problem of behavior **S _{f}(n)** as

where **ν _{j}, μ_{j} = 0** or

Since the integral parts **[A], [x _{0}]** are fixed and

In what follows we call the *bit operations* simply *operations,* omitting the word *bit*.

The next problem is the problem of the total number of bit operations sufficient for computing the product **ab**, or the problem of complexity of multiplication. The function of complexity of multiplication has the special notation **M(n).**

Multiplying two **n** -digit numbers in the ordinary school way, ‘in column’, we actually put together in this case **n n** -digit numbers. So for the complexity of this ‘school’ method or ‘ordinary’ method we get the upper bound **M(n) = O(n ^{2}).**

In 1956 A. N. Kolmogorov formulated the conjecture, that the low bound for **M(n)** for any method of performing the multiplication is also of order **n ^{2}** (the so-called Kolmogorov

In 1960 A. Karatsuba [20], [21], [22] (see also [36]) found a method of multiplication with the complexity bound

and thus disproved the **‘n ^{2} -conjecture’.** Later the method was called

The appearance of the method **‘Divide and Conquer’** was the starting point of the theory of fast computations. A number of authors (among them Toom [51], Cook [15], and Schönhage [45]) continued to look for an algorithm of multiplication with the complexity close to the optimal one, and in 1971 Schönhage and Strassen [46], [47] constructed an algorithm with the best known (at present) upper bound for **M(n).**

In the construction of this algorithm, apart from **‘Divide and Conquer’**, they used the idea of realizing arithmetic operations modulo the Fermat numbers **2 ^{2n}+ 1**, and the

On the basis of the method **‘Divide and Conquer’** the algorithms of fast matrix multiplication were constructed. Strassen [50] was the first to find such algorithm in 1970, later these investigations were continued by Coppersmith and Winograd [16], Pan [43] and others.

Approximately at the same time the first algorithms of calculation of elementary algebraic functions started to appear. As it was already mentioned before, the division of the number **a** by the number **b** with residue, that is the calculation of the numbers **q** and **r** in the formula

is reduced to addition-subtraction and multiplication, and if **a** and **b** are **n** -digit numbers, then the complexity of division is **O(M(n)).**

The simplest algorithm of division is to compute the inverse value **1/b** with accuracy up to **n** digits by the **Newton method** and after that to multiply by **a** using the fast multiplication algorithm.

Assume that we must find **x = 1/b,** where **1/2 ≤ b ≤ 1** (if this is not true, then multiplying or dividing by **2 ^{N}** we obtain the example under consideration). As an initial approximation we take

This method provides sufficiently fast convergence to **1/b**, since from the equality **x _{n} = 1/b – ε**, it follows

For taking the root of **k** -th degree from a number, that is for the calculation of **a ^{1/k},** it is also possible to use the

Note that multiplying or dividing by **2 ^{kN},** one can always get the condition

First fast algorithms of computation of elementary algebraic functions based on the **Newton method** appear in the works of Cook [15],
Bendersky [8] and Brent [11] (see also [36]). Using **Newton's method,** it is possible to prove also the following theorem ([11]):

**Theorem.** *If the equation* **f(x) = 0** *has a simple root* **ζ ≠ 0, f(x)** *is Lipschitz continuous in the neighborhood* **ζ,** *and we can compute* **f(x)** *with accuracy up to* **n** *digits by* **O(M(n)j(n))** *operations, where* **j(n)** *is a positive, monotone increasing function for any* **x** *from a neighborhood of* **ζ,** *then it is possible to calculate* **ζ** *with accuracy up to* **n** *digits also by* **O(M(n)j(n))** *operations.*

In 1976 Salamin [44] and Brent [11] suggested first algorithm for fast evaluation of the constant **π** based on the **AGM**-method of Gauss (see, for example, [13], [14]). Using also the ascending transformations of Landen [39], Brent [11] suggested the first **AGM**-algorithms for evaluation of elementary transcendental functions. Later many authors have been going on to study and use the **AGM**-algorithms. Among those authors were the brothers Jonathan Borwein and Peter Borwein, who wrote the book ‘The Pi and the AGM’ [9], where the greatest number of **AGM**-algorithms were collected. Apart from the algorithms of calculation of elementary transcendental functions, in this book there were also algorithms for evaluation of some higher transcendental functions (the Euler Gamma function,for example). To compute such functions with accuracy up to **n** digits using the algorithms described in the book one needs

operations.

About some other results connected with **‘Divide and Conquer’** and fast calculations see [1], [2], [3], [6], [7], [17], [18], [36], [41].

An algorithm of computation of a function **f = f(x),** is said to be *fast,* if for this algorithm

where **c** is a constant. Here and below we assume that for **M(n)** the Schönhage-Strassen bound holds. It is obvious that for any algorithm and any function **f,** the inequality

is valid. (Note that recording some number with accuracy up to n digits requires itself not less than **n + 1** operations.) Therefore, for fast algorithms

for any **ε > 0** and **n > n _{1}(ε).** That is, for the fast computational algorithms the order of upper bound of

The method **FEE** (since 1990) [23]-[35] (see also [4]-[6], [40]) is at present the second known method (after the **AGM**) for fast evaluation of classical constants **e** and **π,** and elementary transcendental functions. But, unlike the **AGM,** the **FEE** is also the method for fast computation of higher transcendental functions. At present the **FEE** is the unique method, permitting to calculate fast such higher transcendental functions as the Euler Gamma function, hypergeometric, spherical, cylindrical etc. functions for algebraic values of the argument and parameters, the Riemann zeta function for integer values of the argument and the Hurwitz zeta function for integer values of the argument and algebraic values of the parameter.

The main idea of the method **FEE** is explained in the easiest way by the example of calculating the classical constant **e.** To begin with, we consider the algorithm of computation of **n!** in **log n** steps with the complexity

For simplicity we assume that **n = 2 ^{k}, k ≥ 1.**

**Step 1.** Calculate **n/2** products of the form:

**Step 2.** Calculate **n/4** products of the form:

**... etc.**

**Step k, the last one.** Calculate one product of the form:

This gives the result: **n!**

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

Here we choose **m,** requiring that for the remainder **R _{m}** the inequality

We calculate the sum

in **k** steps of the following process.

**Step1.** Combining in **S** the summands sequentially in pairs we carry out of the brackets the ‘obvious’ common factor and obtain

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

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

**m _{1} = m/2, m = 2^{k}, k ≥ 1.**

At the first step **m/2** integers of the form

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 ≤k).**

**m _{i+1} = m_{i}/2 = m/2^{i+1}, **

we compute only **m/2 ^{i+1}** integers of the form

**j = 0, 1, ... , m _{i+1} – 1, m = 2^{k}, k ≥ i+1**. Here

**... etc.**

**Step k, the last one.** We compute one integer value **α _{1}(k),** we compute, using the fast algorithm described above the value

The method was called **FEE (Fast E-function Evaluation)** for the reason that it makes it possible to compute fast the Siegel **E -functions,** and in particular, **e ^{x}.** A class of functions, which are ‘similar to the exponential function’ was given the name

and apply the **FEE** to sum the Taylor series for

arctan 1/3 = 1/(1 * 3) – 1/(3 * 3

with the remainder terms **R _{1},
R_{2},** which satisfy the bounds

| R

and for **r = n, 4( |R _{1}| + | R_{1}| ) < 2^{–n}.**

To calculate **π** by the **FEE** it is possible to use also other approximations, for example from [5]. The complexity is

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, k = n, k ≥ 1,**

The complexity is

To evaluate fast the constant **γ** it is possible to apply the **FEE** to the approximation from [12].

By the **FEE** the two following series are calculated fast:

under the assumption that **a(j), b(j)** are integers, **| a(j) | + | b(j) | ≤ (Cj) ^{K} ; | z | < 1; K** and

S

Consider **y = f(x) = e ^{x}**. We calculate the function

Take the integer **k**, satisfying the conditions **2 ^{k–1} < n ≤ 2^{k}** and set

Then

Let us compute **e ^{xN} .** Represent

where

Here **β _{ν}** is a

We expand each factor of this product in the Taylor series:

**r = N 2 ^{–ν+1} .**

For the remainder of the Taylor series
**R _{ν}(r)** the following inequalities are valid:

**R _{ν}(r) < 2^{–N} .**

Consequently, it is possible to rewrite (4) in the form

where

and the constants **θ _{ν}(r)** satisfy the estimate

It is easy to see that the sum (5) is suitable for summing by means of the **FEE.** At the last step of the process we have in (5)

and then we make one division of the integer **a _{ν}** by the integer

Then **e ^{xN}** can be represented in the form

**| θ _{ν} | ≤ 1 .**

We define the integer ** l** from the inequalities

**| θ _{ν} | ≤ 1 .**

It is clear that **log k ≤ l < log k + 1.**

The last product is computed in ** l** steps of the process, which is similar to calculating

**(η _{ν} + 2 θ_{ν} 2^{–N}) (η_{ν+1}+ 2 θ_{ν+1} 2^{–N}) = η_{ν}η_{ν+1}+ 2 θ_{ν} 2^{–N}η_{ν+1}+ 2 θ_{ν+1}2^{–N} η_{ν} + 4 θ_{ν}θ_{ν+1}2^{–2N} = η_{ν,ν+1}+ 8 θ_{ν,ν+1}2^{–N},**

**ν ≡ 0(2), ν = 2, 3, ... , 2 ^{l}+ 1,**

where

Here we take into account that **| η _{ν} | < e^{xN} < e^{x0} < 3/2 .**

After the **1-st step** of this process the product (6) takes the form:

**ν ≡ 0(2)
| θ _{ν,ν+1} | ≤1 .**

Further we act in a similar way.

After the **2-nd step** of this process the product (6) takes the form:

**ν ≡ 2(4)
| θ _{ν,ν+1,ν+2,ν+3} | ≤ 1 .**

In ** l steps** we obtain

**| θ _{2, ..., 2l+1} | ≤ 1 .**

Since ** l < log k + 1, k = log N – 1, 2n ≤ N < 4n,** we find from the last relation that

where **η = η _{2, ..., 2l+ 1} , | θ | ≤ 1 .**

The complexity of the computation of **e ^{x0}** with the help of this process is

**Remark 1.** *We considered the case* **0 < x _{0} < 1/4 .**

Computation of the trigonometric functions **y = f(x) = sin x** and **y = f(x) = cos x** at the point **x = x _{0}** can be reduced to the computation of real and imaginary parts of

**| θ _{1-} | ≤ 1 .**

We write

in the form

where

**0 < θ _{ν}(r) < 1.**

Then we perform with the sums (8), (9) the same actions as with the sum (4). Let **η _{ν} ,**

Then (7) can be represented in the form

**| θ _{ν} | ≤ 1 .**

We compute the product (10) by means of the process which is described in the previous paragraph. As a result we find with specially chosen *l*, N, r

whence

The complexity of the evaluation is the same as for the exponential function:

In [26] the following general theorem is proved:

**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. Then*

The Euler gamma function **y = Γ(s)**, is one of those higher transcendental functions, that, being not Siegel E-functions, at the same time can be calculated fast by the **FEE.** There are two algorithms for the evaluation of **Γ(s):** 1) for rational values of the argument **s;** 2) for algebraic values of the argument **s.** The first of these algorithms is more ‘simple’ than the second one. We compute the function **y = Γ(x) ,** for **x = x _{0} = a/b ; (a,b) = 1 ,** assuming at first that

It is easy to see that for **p = n, 0 < x _{0} < 1 ,**

Hence,

**0 < θ _{1} < 3/4**.

Assuming that **r ≥ 3n** , we expand the integrand in (11) in the Taylor series in powers of **t:**

where **R _{r} = θ_{r} t^{r+1}/(r+1)! , | θ_{r} | ≤ 1 .** From here we have for

where

and we will calculate **Γ(x _{0}) = Γ(a/b)** by (12)-(13). We note, that for the calculation of the value

Then it is possible to rewrite (13) in the form

We compute the sum **S** by the **FEE** in **k** steps, combining at each step the summands of **S** sequentially in pairs and taking out of the brackets the ‘obvious’ common factor. However, unlike the computation of the constant **e** now in each pair of the brackets there are fractions, not integers. So that at each step we calculate the integer numerator and the integer denominator of the fraction, sitting in each pair of brackets (we do not divide until the last step). At the first step we have

At the **1-st step** we calculate the integers

At the **j**-th step (**j ≤ k**) we have

where **S _{rj–ν}(j) ; ν = 0, 1, ... , r_{j}–1 ;** are defined by the equalities

At the **j-th step (j ≤ k)** we calculate the integers

**ν = 0, 1, ... , r _{j}–1 ; r_{j} = (r + 1)/2^{j} .**

**... etc.**

At the **k-th (the last) step** we calculate the integers **p _{rk}(k) = p_{1}(k) , q_{rk}(k) = q_{1}(k) , r!** and make one division with accuracy

which gives the sum **S** with accuracy **2 ^{–n–1} . ** Hence

**Remark 2.** *We evaluated* **Γ(x _{0}),
x_{0} = a/b , **

We shall evaluate **Γ(x _{0}) ,** where

**g _{μ}, g_{μ–1}, ..., g_{0}** are integers,

that is

where

The computation of **S** is realized in **k** steps, **r+1 = 2 ^{k} , 2^{k–1} < 6n ≤ 2^{k} , k ≥ 1 .** The peculiarity of this algorithm is that we use the main property of algebraic numbers to bound the growth of the computational complexity. Before the step

At the

and we calculate the integers

**ν = 0, 1, ... , (r+1)/2–1.**

At **i-th step** in brackets there are the numbers

where

and we calculate the integers

**0 ≤ m _{1} ≤ 2^{i–1}–1 , 0 ≤ m_{2} ≤ 2^{i–1} .**

**0 ≤ l_{1} ≤ 2^{i–1} , 0 ≤ l_{2} ≤ 2^{i–1} .**

Note that the multiplication by the power of **α** and the computation of **δ** and **ρ ,** also the division of **δ** by **ρ , ** are not produced till the last step.

Before the **i+1 -st step (1 ≤ i ≤k , 2 ^{i–1} < μ ≤ 2^{i})** we reduce the polynomials (19) modulo polynomial

where **p _{t–1} , ..., p_{0} , q_{t} , ..., q_{0}** are integers,

where **P _{1}(x)** and

that is, in (18) we get

Multiplying, if necessary the numerator and the denominator of the fraction (20) by an integer common factor, we get in the numerator and the denominator of the fractions ‘in brackets’ the polynomials with integer coefficients of degree not higher than **μ–1 .** Starting with **i ,** at each step **i ,
i+1 , ... , k ,** we reduce the polynomials in **α , ** sitting in the numerator and the denominator of **β _{ξ}(j) ** modulo

what does not make any influence on the bound of the complexity of the calculations we perform. At the last, **k** -th, step of this process we get

where

**p, q ≤ μ–1 , ** and we calculate **δ _{rk}(k) , ρ_{rk}(k) ** and

The presented method **FEE,** the method of fast summation of series of a special form, permits to compute any elementary transcendental function for any value of the argument, the classical constants **e, π,** the Euler constant **γ,** the Catalan and the Apery constants, such higher transcendental functions as the Euler gamma function and its derivatives, the hypergeometric, spherical, cylindrical and other functions for algebraic values of the argument and parameters, the Riemann zeta function for integer values of the argument and the Hurwitz zeta function for integer argument and algebraic values of the parameter, and also such special integrals as the integral of probability, the Fresnel integrals, the integral exponential function, the integral sine and cosine, and some other integrals for algebraic values of the argument with the complexity bound which is close to the optimal one, namely

At present, only 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's and Apery's constants. An additional advantage of the method **FEE** is the possibility of parallelizing the algorithms based on the **FEE.**

The concept of **complexity of computation**
arose as a result of development of computational methods
and information theory.

Among the first investigations in the field of information theory were the works of Harry Nyquist [42] and Ralph Hartley [19], where the concept of the measure of information was introduced.

We considered above the bit complexity, that defines the measure of efficiency of real calculations in the most sharp way. At the same time, for different problems it is possible to define the measure of efficiency of computations in different ways. Thus along with the bit complexity, there are also the algebraic, Boolean, Kolmogorov, rational etc. complexities. Some of them are determined by the amount of the bit, algebraic, etc. operations spent for the calculation; the others—by the number of steps of the computational process, for example, by the number of steps of work of the Turing machine.

The first algorithm that was analyzed from the viewpoint of its complexity, was, it seems, the Euclidean algorithm for computing the greatest common divisor of two integers. Its complexity was measured by the total number of steps-divisions in this algorithm. The bounds for complexity of the Euclidean algorithm were obtained [48] by Antoine-André-Louis Reynaud (a rough estimate of the total number of steps of the algorithm, 1811), Pierre-Joseph-Étienne Finck (an estimate of the number of steps of the algorithm, close to the optimal one, 1841) and Gabriel Lamé (the optimal estimate, 1844). The last result is known in the literature as the Lamé theorem.

Constructing algorithms of evaluation for a broad class of
functions with the bit complexity bound which is close to the optimal one,
and also obtaining non-trivial lower bounds of the bit complexity, are
the main problems in the field which is called **fast algorithms** or
**fast computations**. At present, there are many unsolved problems in
this field, such as

–
obtaining a nontrivial lower bound for the complexity of multiplication
or for the complexity of evaluation of a transcendental function;

–
constructing fast algorithms for computation of a higher transcendental
function at transcendental points;

–
constructing fast algorithms for calculation of such constants as the Brun
constant;
the values of the Riemann zeta function at non-integral points, etc.

These and many other problems in the field of fast computations are still waiting for their solutions.

[1] **V.B.Alekseev,** From the Karatsuba Method for Fast Multiplication of Numbers to Fast Algorithms for Discrete Functions. Proceddings of the Steklov Inst.of Math., v.218, pp.15-22 (1997).

[2] **V.B.Alekseev, S.A.Lozkin,** Elements of graph theory, circuits and automata. Publ. VMK MGU, 58 pp., Moscow (2000).

[3] **G.N.Arkhipov, V.N. Chubarikov, V.A. Sadovnichii,** Lectures in Mathematical Analysis. Publ. ‘Vysshaya Shkola’,
695 pp., Moscow (1999).

[4] **E.Bach,** The complexity of number-theoretic constants. Info.Proc.Letters, N 62, pp.145-152 (1997).

[5] **D.H.Bailey, P.B.Borwein** and **S.Plouffe,** On the rapid computation of various polylogarithmic constants.
Math. Comp., v.66, pp.903-913 (1997).

[6] **J.C.Bajard, J.M.Muller,** Calcul et arithmetique des ordinateurs. Hermes Science, 226 pp. (2004).

[7] **L.A.Bassalygo,** Note on fast multiplication of polynomials over Galois fields. Probl. of Inform.Transm., 14 (1), pp.71-72 (1978).

[8] **Benderskij Yu.V.,** Fast Computations. Dokl.Akad.Nauk SSSR, v.223, N 5, pp.1041-1043 (1975).

[9] **J.M.Borwein** and **P.B.Borwein,** Pi and the AGM. Wiley, 414 pp., New York (1987).

[10] **J.M.Borwein, D.M.Bradley** and **R.E.Crandall,** Computational strategies for the Riemann zeta function.
J. of Comput. Appl. Math., v.121, N 1-2, pp.247-296 (2000).

[11] **R.P.Brent,** Fast Multiple-Precision Evaluation of Elementary Functions. ACM, v.23, N 2, pp.242-251 (1976).

[12] **R.P.Brent** and **E.M.McMillan,** Some new algorithms for high-precision computation of Euler's constant.
Math. Comp., v.34, pp.305-312 (1980).

[13] **B.C.Carlson,** Algorithms involving arithmetic and geometric means. Amer. Math. Monthly, v.78, pp.496-505 (1971).

[14] **B.C.Carlson,** An algorithm for computing logarithms and arctangents. Math.Comp., v.26, pp.543-549 (1972).

[15] **S.A.Cook,** On the minimum computation time of functions. Thesis, Harvard University (1966).

[16] **D.Coppersmith** and **S.Winograd,** On the asymptotic complexity of matrix multiplication. SIAM Journal on Computing, v.11, N 3, pp.472-492 (1982).

[17] **S.B.Gashkov,** On the Complexity of Integration of Rational Fractions. Proceedings of the Steklov Inst.of Math.,
v.218, pp.122-133 (1997).

[18] **S.B.Gashkov, V.N. Chubarikov,** Arithmetics. Algorithms. The Complexity of Computations. Publ. ‘Vysshaya Shkola’, 2-d ed., 320 pp., Moscow (2000).

[19] **R.V.L.Hartley,** Transmission of Information. Bell System Technical Journal, v.7, pp.535-563 (1928).

[20] **Karatsuba A.** and **Ofman Yu.,** Multiplication of Multiplace Numbers on Automata. Dokl.Akad.Nauk SSSR, v.145, N 2, pp.293-294 (1962).

[21] **A.Karacuba,** Berechnungen und die Kompliziertheit von Beziehungen. EIK, N 11, pp.10-12 (1975).

[22] **A.A.Karatsuba,** The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics, v.211, pp.169-183 (1995).

[23] **Karatsuba E.A.,** Fast computation of **exp(x).** Problems of Information Transmission, v.26, N 3, p.109, Chronicle-17th All-Union School on Theory of Information and its Applications (1990).

[24] **Karatsuba E.A.,** On a new method for fast evaluation of transcendental functions. Uspechi Mat. Nauk, v.46, N 2 (278), pp.219-220 (1991).

[25] **Karatsuba E.A.,** On the fast computation of transcendental functions. Doklady Akad. Nauk SSSR, v.319, N 2, pp.278-279 (1991).

[26] **Karatsuba E.A.,** Fast evaluations of transcendental functions. Probl. Peredachi Informat., v.27, N 4, pp.87-110 (1991).

[27] **Karatsuba E.A.,** Fast evaluation of **ζ(3).** Probl. Peredachi Informat., v.29, N 1, pp. 68-73 (1993).

[28] **Catherine A.Karatsuba,** Fast evaluation of Bessel functions. Integral Transforms and Special Functions, v.1,
N 4, pp.269-276 (1993).

[29] **Karatsuba E.A.,** Fast Evaluation of Riemann zeta-function **ζ(s)** for integer values of argument **s**. Probl. Peredachi Informat., v.31, N 4, pp.69-80 (1995).

[30] **Karatsuba E.A.,** On fast computation of Riemann zeta-function for integer values of argument. Doklady RAS, v.349, N 4, p.463 (1996).

[31] **Karatsuba E.A.,** Fast evaluation of Hurwitz zeta function and Dirichlet **L** -series, Problem. Peredachi Informat., v.34, N 4, pp.342-353 (1998).

[32] **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., pp.303-314 (1999).

[33] **E.A.Karatsuba,** On the computation of the Euler constant gamma. University of Helsinki preprint, 21 pp. (1999);
J. of Numerical Algorithms, v.24, pp.83-97 (2000).

[34] **E.A.Karatsuba,** Fast computation of **ζ(3)** and of some special integrals, using the polylogarithms, the Ramanujan formula and it's generalization. J. of Numerical Mathematics BIT, v. 41, N 4, pp.722-730 (2001).

[35] **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., pp.29-41 (2001).

[36] **D.E.Knuth,** The art of computer programming. v.2 Addison-Wesley Publ.Co., 724 pp., Reading (1969).

[37] **A.N.Kolmogorov,** Asymptotic characteristics of some completely bounded metric spaces. Dokl. Akad. Nauk SSSR, v.108, N 3, pp.385-388 (1956).

[38] **A.N. Kolmogorov,** Information Theory and the Theory of Algorithms. Publ. Nauka, 303 pp., Moscow (1987).

[39] **J.Landen,** An investigation of a general theorem for finding the length of any arc of any conic hyperbola, by means of two elliptic arcs, with some other new and useful theorems deduced therefrom. Philos.Trans.Royal Soc. London, v.65, pp.283-289 (1775).

[40] **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, v.48, pp.79-125 (1994).

[41] **V.I.Nechaev,** Elements of Cryptography. Basic Protection Information Theory. Publ. ‘Vysshaya Shkola’, 110 pp., Moscow (1999).

[42] **H. Nyquist,** Certain factors affecting telegraph speed. Bell System Technical Journal, v. 3, pp. 324-346 (1924).
[43] **V.Ya.Pan,** Strassen's algorithm is not optimal. Proc. ACM Symp. on the Found. of Comp.Science, pp.166-176 (1978).

[44] **E.Salamin,** Computation of **π** using arithmetic-geometric mean. Math. Comp., v.30, N 135, pp.565-570 (1976).

[45] **A.Schönhage,** Schnelle Multiplikation grosser Zahlen. Computing, v.1, pp.182-196 (1966).

[46] **A.Schönhage** und **V.Strassen,** Schnelle Multiplikation grosser Zahlen. Computing, v.7, pp.281-292 (1971).

[47] **A. Schönhage, A. F. W. Grotefeld and E. Vetter**, Fast Algorithms — A Multitape Turing Machine Implementation. BI-Wiss.-Verl., 300 pp., Zürich (1994).

[48] **J. Shallit,** Origins of the Analysis of the Euclidean Algorithm. Historia Mathematica, v.21, pp.401-419 (1994).

[49] **C.L.Siegel,** Transcendental numbers. Princeton University Press, 102 pp., Princeton (1949).

[50] **V.Strassen,** Gaussian elimination is not optimal. J. Numer. Math., N 13, pp.354-356 (1969).

[51] **A.L.Toom,** The complexity of a scheme of functional elements realising the multiplication of integers.
Dokl.Akad.Nauk SSSR, v.150, N 3, pp.496-498 (1963).

**About the FEE see E.A.Karatsuba's paper:**

‘**Fast evaluation of Hurwitz zeta function and Dirichlet L-series**’.

Problem. Peredachi Informat., v.34, N 4, pp.342-353 (1998).

*) If any mathematical symbols or formulas are not visible correctly than you can see them in the same file

- in MS-Word format (220 672 bytes);
- HTML (431 870 bytes) (It need to download the Vector Graphic Rendering component);

II. THE FEE METHOD

1. Introduction. Definition of a fast algorithm

2. Calculation of the constant

3. The method

4. Calculation of the exponential function by the

5. Calculation of the trigonometric functions by the

6. Fast evaluation of the Euler gamma function for a rational value of the argument

7. Fast evaluation of the Euler gamma function for an algebraic argument

8. Conclusion

III. ON THE COMPLEXITY OF COMPUTATIONS

References

© Ekatherina Karatsuba

The allocation date is May 18, 2005.

Last correction: March 18, 2013.