Fast algorithms - Revision history

Jlwoodwa: +rcat

2024-05-03T21:28:21Z

+rcat

← Previous revision		Revision as of 21:28, 3 May 2024
Line 1:		Line 1:
	#REDIRECT [[Time complexity]]		#REDIRECT [[Time complexity]]

			{{rcatsh\|
			{{r hist}}
			}}

Miym: Time complexity

2010-01-10T20:27:39Z

Time complexity

← Previous revision		Revision as of 20:27, 10 January 2010
Line 1:		Line 1:
	#REDIRECT [[~~Analysis~~ ~~of algorithms~~]]		#REDIRECT [[Time complexity]]

Spitfire: Reverted edits by 85.141.97.109 to last revision by RobinK (HG)

2009-11-13T21:08:27Z

Reverted edits by 85.141.97.109 to last revision by RobinK (HG)

← Previous revision	Revision as of 21:08, 13 November 2009
Line 1:	Line 1:
		#REDIRECT [[Analysis of algorithms]]

85.141.97.109: ←Blanked the page

2009-11-13T21:08:02Z

←Blanked the page

← Previous revision		Revision as of 21:08, 13 November 2009
Line 1:		Line 1:
	#REDIRECT [[Analysis of algorithms]]

RobinK: Notability not clear and concept can be explained in 1 sentence at analysis of algorithms

2009-08-22T17:45:40Z

Notability not clear and concept can be explained in 1 sentence at analysis of algorithms

← Previous revision		Revision as of 17:45, 22 August 2009
Line 1:		Line 1:
			#REDIRECT [[Analysis of algorithms]]
	{{Context\|date=August 2009}}
	{{Notability\|date=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 <math>0,1,+,-, (,)</math>, 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 [[Context of computational complexity\|bit complexity]] which is
	denoted <math>s_f(n) = s_{f,x_0}(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
	:<math>s_f(n)= O\left(M(n)\log^cn\right) \ ,</math>
	where ''c'' 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,
	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,
	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.

	==See also==
	*[[Computational complexity theory]]

	==References==
	<references/>

	==External links==
	*http://www.ccas.ru/personal/karatsuba/divcen.htm
	*http://www.ccas.ru/personal/karatsuba/algen.htm

	{{DEFAULTSORT:Fast Algorithms}}
	[[Category:Algorithms]]

	[[ru:Быстрые алгоритмы]]

SmackBot: Date maintenance tags and general fixes

2009-08-22T16:11:18Z

Date maintenance tags and general fixes

← Previous revision		Revision as of 16:11, 22 August 2009
Line 1:		Line 1:
			{{Context\|date=August 2009}}
	{{context}}
			{{Notability\|date=August 2009}}
	{{notability}}
	'''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.		'''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.

Line 27:		Line 27:
	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,		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,
	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.		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.

⚫	==References==
⚫	<references/>

	==See also==		==See also==
	*[[Computational complexity theory]]		*[[Computational complexity theory]]

		⚫	==References==
		⚫	<references/>

	==External links==		==External links==
Line 38:		Line 38:
	*http://www.ccas.ru/personal/karatsuba/algen.htm		*http://www.ccas.ru/personal/karatsuba/algen.htm

			{{DEFAULTSORT:Fast Algorithms}}
	[[Category:Algorithms]]		[[Category:Algorithms]]

CRGreathouse: cleanup links, See also, boldface, wording

2009-08-21T07:07:07Z

cleanup links, See also, boldface, wording

← Previous revision		Revision as of 07:07, 21 August 2009
Line 1:		Line 1:
	{{context}}		{{context}}
	{{notability}}		{{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 ==		== 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) ==		== 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 ==		== 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 ==		== 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==		==References==
Line 54:		Line 32:

	==See also==		==See also==
	*[[Complexity of computation (bit)]]
	*[[Computational complexity theory]]		*[[Computational complexity theory]]
	*[[The AGM method of Gauss]]
	*[[The FEE method]]
	*[[The Karatsuba multiplication]]

	==External links==		==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]]		[[Category:Algorithms]]

Pcap: /* Complexity of computation (bit) */ ok, let's just link to that article instead of providing out of date info

2009-08-21T00:10:37Z

Complexity of computation (bit): ok, let's just link to that article instead of providing out of date info

← Previous revision		Revision as of 00:10, 21 August 2009
Line 21:		Line 21:
	<math>s_f(n) = s_{f,x_0}(n).</math>		<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 function of
⚫	complexity of multiplication has the special notation <math>M(n)</math>.

	The [[Schönhage–Strassen algorithm\|best known]] (at present) upper bound for <math>M(n),</math> is

	: <math>M(n) = O(n \log n \log\log n).\,</math>

	== Fast algorithm of computation of a function ==		== Fast algorithm of computation of a function ==

Pcap: /* Complexity of computation (bit) */ oops

2009-08-21T00:05:47Z

Complexity of computation (bit): oops

← Previous revision		Revision as of 00:05, 21 August 2009
Line 24:		Line 24:
	complexity of multiplication has the special notation <math>M(n)</math>.		complexity of multiplication has the special notation <math>M(n)</math>.

	The best known (at present) upper bound for <math>M(n),</math> is		The [[Schönhage–Strassen algorithm\|best known]] (at present) upper bound for <math>M(n),</math> is

	: <math>M(n) = O(n \log n \log\log n).\,</math>~~{{dubious}}{{fact}}~~		: <math>M(n) = O(n \log n \log\log n).\,</math>

	== Fast algorithm of computation of a function ==		== Fast algorithm of computation of a function ==

Pcap: /* Complexity of computation (bit) */ seems wrong

2009-08-20T23:57:34Z

Complexity of computation (bit): seems wrong

← Previous revision		Revision as of 23:57, 20 August 2009
Line 26:		Line 26:
	The best known (at present) upper bound for <math>M(n),</math> is		The best known (at present) upper bound for <math>M(n),</math> is

	: <math>M(n) = O(n \log n \log\log n).\,</math>		: <math>M(n) = O(n \log n \log\log n).\,</math>{{dubious}}{{fact}}

	== Fast algorithm of computation of a function ==		== Fast algorithm of computation of a function ==