Fast algorithms

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.

Bit operation

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.

Complexity of computation (bit)

To estimate the quality of a fast method or algorithm is used the function of complexity of computation (bit).

Define what it means to evaluate a function at a given point.

We consider the simplest case: let $y=f(x)$ be a real function of a real argument $x,\ \ a\leq x\leq b$, and assume that $f(x)$ satisfies on $(a,b)$ the Lipschitz condition of order $\alpha$, $0<\alpha <1,$ that is for $x_{1},x_{2}\in (a,b):$ $|f(x_{1})-f(x_{2})|\leq |x_{1}-x_{2}|^{\alpha }.$ Let $n$ be a natural number.

Def.2 To compute the function $y=f(x)$ at the point $x=x_{0}\in (a,b)$ up to $n$ digits (with accuracy $2^{-n}$) means to find such a number $A,$ that $|f(x_{0})-A|\leq 2^{-n}.$

Def.3 The total number of bit operations 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. Thus, the complexity of computation of $f(x)$ at the point $x=x_{0}$ is a function of $n$ and so are $f(x)$ and $x=x_{0}.$ This function is denoted by $s_{f}(n)=s_{f,x_{0}}(n).$

It is clear that $s_{f}(n)$ 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 sometimes treated as a 'time' function $T(n)$.

The problem of behavior of $s_{f}(n)$ as $n\to \infty$ for a class of functions or for a particular function $f$ was for the first time formulated by Kolmogorov around 1956.

History of the problem

The field Fast Algorithms was born in 1960 , when the first fast method --- the Karatsuba multiplication --- was found. Later the Karatsuba method was called “Divide and Conquer” (sometimes any method of computation with subdivisions is called with the same name), other names which people use for the method invented by Karatsuba are “Binary Splitting”,"Dichotomy Principle" etc. After the Karatsuba method, many other fast methods were constructed, including the Strassen fast matrix multiplication method (the generalization of the Karatsuba idea for matrices), the Schönhage-Strassen multiplication method etc . Some old methods become fast computational methods with use of one of the fast multiplication algorithms, such as the Newton method for calculation of elementary algebraic functions and the AGM method of Gauss for evaluation of elementary transcendental functions.

See also

• Computational complexity theory