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.

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 Schonhage-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.

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