Fast algorithms: Difference between revisions

Content deleted Content added

Inline

Revision as of 07:07, 21 August 2009

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)

The quality of a fast method or algorithm is determined by its bit complexity which is denoted $s_{f}(n)=s_{f,x_{0}}(n).$

The bit complexity of multiplication has the special notation $M(n)$ .

Fast algorithm of computation of a function

An algorithm computing the function $f=f(x)$ is said to be fast if, assuming the best bound for $M(n)$ , for this algorithm

s_{f}(n)=O\left(M(n)\log ^{c}n\right)\ ,

where c is a constant.

History of the problem

The field fast algorithms was born in 1960^[1], when the first fast method—the Karatsuba algorithm—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^[2], including the Strassen algorithm^[3] (the generalization of the Karatsuba idea for matrices), the Schönhage–Strassen algorithm^[4]^[5], the FEE method^[6]^[7] for evaluation elementary and higher transcendental functions etc . Some old methods become fast computational methods with use of one of the fast multiplication algorithms, such as Newton's method for calculation of elementary algebraic functions and the AGM method of Gauss for evaluation of elementary transcendental functions.

References

^ A.A. Karatsuba, The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics, Vol.211 (1995)
^ D.E. Knuth, The art of computer programming. Vol.2 Addison-Wesley Publ.Co., Reading (1969).
^ V. Strassen, Gaussian elimination is not optimal. J. Numer. Math., N 13 (1969)
^ A. Schönhage und V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing, Vol.7 (1971)
^ A. Schönhage, A.F.W. Grotefeld and E. Vetter, Fast Algorithms. BI-Wiss.-Verl., Zürich (1994).
^ E.A. Karatsuba,Fast evaluations of transcendental functions. Probl. Peredachi Informat., Vol. 27, N 4 (1991).
^ 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).

External links

[1] A.A. Karatsuba, The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics, Vol.211 (1995)

[2] D.E. Knuth, The art of computer programming. Vol.2 Addison-Wesley Publ.Co., Reading (1969).

[3] V. Strassen, Gaussian elimination is not optimal. J. Numer. Math., N 13 (1969)

[4] A. Schönhage und V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing, Vol.7 (1971)

[5] A. Schönhage, A.F.W. Grotefeld and E. Vetter, Fast Algorithms. BI-Wiss.-Verl., Zürich (1994).

[6] E.A. Karatsuba,Fast evaluations of transcendental functions. Probl. Peredachi Informat., Vol. 27, N 4 (1991).

[7] 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).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{context}}
 {{notability}}
-'''Fast algorithms''' is the field of computational mathematics that
+'''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.
-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
+We assume that numbers are written in the binary form, the signs of which 0 and 1 are called bits.
-which 0 and 1 are called '''bits'''.
-'''Def.1.''' Writing down of one of the symbols  <math>0,1,+,-, (,)</math>, putting
+'''Def.1.''' Writing down of one of the symbols  <math>0,1,+,-, (,)</math>, putting together, subtraction and multiplication of two bits is called an elementary operation or a bit operation.
-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
+The quality of a fast method or algorithm is determined by its [[Context of computational complexity|bit complexity]] which is
+denoted <math>s_f(n) = s_{f,x_0}(n).</math>
-'''[[Complexity of computation (bit)|complexity of computation]]''' (bit) which is
-denoted by
-<math>s_f(n) = s_{f,x_0}(n).</math>
-The function of complexity of [[Multiplication_algorithm#Multiplication_algorithms_for_computer_algebra|multiplication]] has the special notation <math>M(n)</math>.
+The bit complexity of [[Multiplication algorithm|multiplication]] has the special notation <math>M(n)</math>.
 == Fast algorithm of computation of a function ==
+An algorithm computing the function <math>f = f(x)</math> is said to be '''fast''' if, assuming the best bound for <math>M(n)</math>, for this algorithm
-An algorithm of computation of a function
+:<math>s_f(n)= O\left(M(n)\log^cn\right) \ ,</math>
-<math>f = f(x)</math> is said to be '''fast''' if, assuming
+where ''c''  is a constant.
-the best bound for <math>M(n)</math>,
-for this algorithm
-: <math>
-s_f(n)= O\left(M(n)\log^cn\right) \ ,
-</math>
-where <math>c</math>  is a constant.
 == History of the problem ==
+The field fast algorithms was born in 1960<ref>A.A. Karatsuba, The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics, Vol.211 (1995)</ref>, when the first fast method—the [[Karatsuba algorithm]]—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 [[Anatolii Alexeevitch Karatsuba|Karatsuba]] are “Binary Splitting”,"Dichotomy Principle" etc. After the Karatsuba method, many other fast methods were constructed<ref>D.E. Knuth, The art of computer programming. Vol.2 Addison-Wesley Publ.Co., Reading (1969).</ref>, including the [[Strassen algorithm]]<ref>V. Strassen,
-The field fast algorithms was born in 1960 <ref>A.A. Karatsuba,
+Gaussian elimination is not optimal. J. Numer. Math., N 13 (1969)</ref> (the generalization of the Karatsuba idea for matrices), the [[Schönhage–Strassen algorithm]]<ref>A. Schönhage und V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing, Vol.7 (1971)</ref><ref>A. Schönhage, A.F.W. Grotefeld and E. Vetter, Fast Algorithms. BI-Wiss.-Verl., Zürich (1994).</ref>, the [[FEE method]]<ref>E.A. Karatsuba,Fast evaluations of transcendental functions. Probl. Peredachi Informat., Vol. 27, N 4 (1991).</ref><ref>D.W. Lozier and F.W.J. Olver, Numerical Evaluation of Special Functions. Mathematics of Computation 1943-1993: A Half -Century of Computational Mathematics,
-The Complexity of Computations. Proceedings of the Steklov Institute
+W.Gautschi,eds., Proc. Sympos. Applied Mathematics, AMS, Vol.48 (1994).</ref> for evaluation elementary and higher transcendental functions etc . Some old methods become fast computational methods with use of one of the fast multiplication algorithms, such as [[Newton's method]] for calculation of elementary algebraic functions  and  the [[AGM method]] of Gauss  for evaluation of elementary transcendental functions.
-of Mathematics, Vol.211 (1995)</ref>, when the first fast method --- the '''[[The Karatsuba multiplication|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 '''[[Anatolii Alexeevitch Karatsuba|Karatsuba]]''' are “Binary Splitting”,"Dichotomy Principle" etc. After the Karatsuba method, many other fast methods
-were constructed<ref>D.E. Knuth, The art of computer programming. Vol.2 Addison-Wesley Publ.Co., Reading (1969).</ref>, including the '''[[Strassen algorithm|Strassen fast matrix multiplication method]]'''<ref>V. Strassen,
-Gaussian elimination is not optimal. J. Numer. Math., N 13 (1969)</ref> (the generalization of the Karatsuba idea for matrices), the '''[[Schönhage–Strassen algorithm|Schönhage-Strassen multiplication method]]'''<ref>A. Schönhage und V. Strassen, Schnelle Multiplikation grosser Zahlen. Computing, Vol.7 (1971)</ref><ref>A. Schönhage, A.F.W. Grotefeld and E. Vetter, Fast Algorithms. BI-Wiss.-Verl., Zürich (1994).</ref>, the '''[[The FEE method|FEE method]]'''
-<ref>E.A. Karatsuba,Fast evaluations of transcendental functions. Probl. Peredachi
-Informat., Vol. 27, N 4 (1991).</ref><ref>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).</ref>
-for evaluation elementary and higher transcendental functions etc . Some old methods become fast computational methods with use of one of the fast multiplication algorithms, such as the '''[[Newton's method|Newton method]]''' for calculation of elementary algebraic functions  and  the '''[[the AGM method of Gauss|AGM method of Gauss]]'''  for evaluation of elementary transcendental functions.
 ==References==
@@ Line 54: / Line 32: @@
 ==See also==
-*[[Complexity of computation (bit)]]
 *[[Computational complexity theory]]
-*[[The AGM method of Gauss]]
-*[[The FEE method]]
-*[[The Karatsuba multiplication]]
 ==External links==
-*<http://www.ccas.ru/personal/karatsuba/divcen.htm>
+*http://www.ccas.ru/personal/karatsuba/divcen.htm
-*<http://www.ccas.ru/personal/karatsuba/algen.htm>
+*http://www.ccas.ru/personal/karatsuba/algen.htm
 [[Category:Algorithms]]