Multiplication algorithm - Revision history

Henning Makholm: /* Further improvements */ Missing star in the first big-O.

2025-01-25T22:32:40Z

Further improvements: Missing star in the first big-O.

← Previous revision		Revision as of 22:32, 25 January 2025
Line 404:		Line 404:
	=== Further improvements ===		=== Further improvements ===

	In 2007 the [[asymptotic complexity]] of integer multiplication was improved by the Swiss mathematician [[Martin Fürer]] of Pennsylvania State University to <math display="inline">O(n \log n \cdot {2}^{\Theta(\log(n))})</math> using Fourier transforms over [[complex number]]s,<ref name="fürer_1">{{cite book \|first=M. \|last=Fürer \|chapter=Faster Integer Multiplication \|chapter-url=https://ivv5hpp.uni-muenster.de/u/cl/WS2007-8/mult.pdf \|doi=10.1145/1250790.1250800 \|title=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA \|publisher= \|location= \|date=2007 \|isbn=978-1-59593-631-8 \|pages=57–66 \|s2cid=8437794 \|url=}}</ref> where log<sup>*</sup> denotes the [[iterated logarithm]]. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time.<ref>{{cite book \|first1=A. \|last1=De \|first2=C. \|last2=Saha \|first3=P. \|last3=Kurur \|first4=R. \|last4=Saptharishi \|chapter=Fast integer multiplication using modular arithmetic \|chapter-url= \|doi=10.1145/1374376.1374447 \|title=Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC) \|publisher= \|location= \|date=2008 \|isbn=978-1-60558-047-0 \|pages=499–506 \|url= \|arxiv=0801.1416\|s2cid=3264828 }}</ref> In context of the above material, what these latter authors have achieved is to find ''N'' much less than 2<sup>3''k''</sup> + 1, so that ''Z''/''NZ'' has a (2''m'')th root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.		In 2007 the [[asymptotic complexity]] of integer multiplication was improved by the Swiss mathematician [[Martin Fürer]] of Pennsylvania State University to <math display="inline">O(n \log n \cdot {2}^{\Theta(\log^(n))})</math> using Fourier transforms over [[complex number]]s,<ref name="fürer_1">{{cite book \|first=M. \|last=Fürer \|chapter=Faster Integer Multiplication \|chapter-url=https://ivv5hpp.uni-muenster.de/u/cl/WS2007-8/mult.pdf \|doi=10.1145/1250790.1250800 \|title=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA \|publisher= \|location= \|date=2007 \|isbn=978-1-59593-631-8 \|pages=57–66 \|s2cid=8437794 \|url=}}</ref> where log<sup></sup> denotes the [[iterated logarithm]]. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time.<ref>{{cite book \|first1=A. \|last1=De \|first2=C. \|last2=Saha \|first3=P. \|last3=Kurur \|first4=R. \|last4=Saptharishi \|chapter=Fast integer multiplication using modular arithmetic \|chapter-url= \|doi=10.1145/1374376.1374447 \|title=Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC) \|publisher= \|location= \|date=2008 \|isbn=978-1-60558-047-0 \|pages=499–506 \|url= \|arxiv=0801.1416\|s2cid=3264828 }}</ref> In context of the above material, what these latter authors have achieved is to find ''N'' much less than 2<sup>3''k''</sup> + 1, so that ''Z''/''NZ'' has a (2''m'')th root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.

	In 2014, Harvey, [[Joris van der Hoeven]] and Lecerf<ref>{{cite journal		In 2014, Harvey, [[Joris van der Hoeven]] and Lecerf<ref>{{cite journal

Citation bot: Added date. | Use this bot. Report bugs. | Suggested by Dominic3203 | #UCB_toolbar

2025-01-23T11:16:27Z

Added date. | Use this bot. Report bugs. | Suggested by Dominic3203 | #UCB_toolbar

← Previous revision		Revision as of 11:16, 23 January 2025
Line 273:		Line 273:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= The Genius Way Computers Multiply Big Numbers\| website=[[YouTube]]}}</ref>		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= The Genius Way Computers Multiply Big Numbers\| website=[[YouTube]]\| date= 2 January 2025}}</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

Cedar101: /* Schönhage–Strassen */ $\bullet$

2025-01-20T05:49:56Z

Schönhage–Strassen: <math display="block"> \bullet

Cedar101: /* General case with multiplication of N numbers */ $\begin{align}$

2025-01-20T05:43:12Z

General case with multiplication of N numbers: <math display="block"> \begin{align}

← Previous revision		Revision as of 05:43, 20 January 2025
Line 326:		Line 326:
	By exploring patterns after expansion, one see following:		By exploring patterns after expansion, one see following:

	<math> (x_1 B^{ m} + x_0) (y_1 B^{m} + y_0) (z_1 B^{ m} + z_0) (a_1 B^{ m} + a_0) = ~~</math> <br>~~		<math display="block">\begin{alignat}{5} (x_1 B^{ m} + x_0) (y_1 B^{m} + y_0) (z_1 B^{ m} + z_0) (a_1 B^{ m} + a_0) &=
	~~<math>~~ a_1 x_1 y_1 z_1 B^{4m} + a_1 x_1 y_1 z_0 B^{3m} + a_1 x_1 y_0 z_1 B^{3 m} + a_1 x_0 y_1 z_1 B^{3 m} ~~</math> <br>~~		a_1 x_1 y_1 z_1 B^{4 m} &+ a_1 x_1 y_1 z_0 B^{3m} &+ a_1 x_1 y_0 z_1 B^{3 m} &+ a_1 x_0 y_1 z_1 B^{3 m} \\
	~~<math>~~+ a_0 x_1 y_1 z_1 B^{3 m} + a_1 x_1 y_0 z_0 B^{2 m} + a_1 x_0 y_1 z_0 B^{2 m} + a_0 x_1 y_1 z_0 B^{2 m}~~</math>~~ ~~<br>~~		&+ a_0 x_1 y_1 z_1 B^{3 m} &+ a_1 x_1 y_0 z_0 B^{2 m} &+ a_1 x_0 y_1 z_0 B^{2 m} &+ a_0 x_1 y_1 z_0 B^{2 m}\\
	~~<math>~~ + a_1 x_0 y_0 z_1 B^{2 m} + a_0 x_1 y_0 z_1 B^{2 m} + a_0 x_0 y_1 z_1 B^{2 m} + a_1 x_0 y_0 z_0 B^{ m}~~</math> <br>~~		&+ a_1 x_0 y_0 z_1 B^{2 m} &+ a_0 x_1 y_0 z_1 B^{2 m} &+ a_0 x_0 y_1 z_1 B^{2 m} &+ a_1 x_0 y_0 z_0 B^{m\phantom{1}}\\
	~~<math>~~+ a_0 x_1 y_0 z_0 B^{m} + a_0 x_0 y_1 z_0 B^{m} + a_0 x_0 y_0 z_1 B^{ m} + a_0 x_0 y_0 z_0 ~~</math>~~		&+ a_0 x_1 y_0 z_0 B^{m\phantom{1}} &+ a_0 x_0 y_1 z_0 B^{m\phantom{1}} &+ a_0 x_0 y_0 z_1 B^{m\phantom{1}} &+ a_0 x_0 y_0 z_0 \phantom{B^{1 m}}
			\end{alignat}</math>

	Each summand is associated to a unique binary number from 0 to		Each summand is associated to a unique binary number from 0 to
Line 337:		Line 338:
	If we express this in fewer terms, we get:		If we express this in fewer terms, we get:

	<math> \prod_{j=1}^N (x_{j,1} B^{ m} + x_{j,0}) = \sum_{i=1}^{2^{N+1}-1}		<math display="block">\prod_{j=1}^N (x_{j,1} B^{ m} + x_{j,0}) = \sum_{i=1}^{2^{N+1}-1}\prod_{j=1}^N x_{j,c(i,j)}B^{m\sum_{j=1}^N c(i,j)} = \sum_{j=0}^{N}z_jB^{jm}

	\prod_{j=1}^N x_{j,c(i,j)}B^{m\sum_{j=1}^N c(i,j)} = \sum_{j=0}^{N}z_jB^{jm}
	</math>, where <math> c(i,j) </math> means digit in number i at position j. Notice that <math> c(i,j) \in \{0,1\} </math>		</math>, where <math> c(i,j) </math> means digit in number i at position j. Notice that <math> c(i,j) \in \{0,1\} </math>

	<math>		<math display="block">
			\begin{align}

	z_{0} = \prod_{j=1}^N x_{j,0}		z_{0} &= \prod_{j=1}^N x_{j,0}
			\\
	</math><br>
		⚫	z_{N} &= \prod_{j=1}^N x_{j,1}
	<math>
			\\
⚫	z_{N} = \prod_{j=1}^N x_{j,1}
		⚫	z_{N-1} &= \prod_{j=1}^N (x_{j,0} + x_{j,1}) - \sum_{i \ne N-1}^{N} z_i
	</math><br>
			\end{align}
	<math>
⚫	z_{N-1} = \prod_{j=1}^N (x_{j,0} + x_{j,1}) - \sum_{i \ne N-1}^{N} z_i

	</math>		</math>

Cedar101: /* Grid method */ :

2025-01-20T05:28:23Z

Grid method: :

← Previous revision		Revision as of 05:28, 20 January 2025
Line 104:		Line 104:
	\|}		\|}

	followed by addition to obtain 442, either in a single sum (see right), or through forming the row-by-row totals (300 + 40) + (90 + 12) = 340 + 102 = 442.		followed by addition to obtain 442, either in a single sum (see right), or through forming the row-by-row totals
			: (300 + 40) + (90 + 12) = 340 + 102 = 442.

	This calculation approach (though not necessarily with the explicit grid arrangement) is also known as the [[partial products algorithm]]. Its essence is the calculation of the simple multiplications separately, with all addition being left to the final gathering-up stage.		This calculation approach (though not necessarily with the explicit grid arrangement) is also known as the [[partial products algorithm]]. Its essence is the calculation of the simple multiplications separately, with all addition being left to the final gathering-up stage.

BladeX1234: /* Further improvements */ Grammar

2025-01-07T10:48:52Z

Further improvements: Grammar

← Previous revision		Revision as of 10:48, 7 January 2025
Line 409:		Line 409:
	=== Further improvements ===		=== Further improvements ===

	In 2007 the [[asymptotic complexity]] of integer multiplication was improved by the Swiss mathematician [[Martin Fürer]] of Pennsylvania State University to <math display="inline">O(n \log n \cdot {2}^{\Theta(\log(n)})</math> using Fourier transforms over [[complex number]]s,<ref name="fürer_1">{{cite book \|first=M. \|last=Fürer \|chapter=Faster Integer Multiplication \|chapter-url=https://ivv5hpp.uni-muenster.de/u/cl/WS2007-8/mult.pdf \|doi=10.1145/1250790.1250800 \|title=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA \|publisher= \|location= \|date=2007 \|isbn=978-1-59593-631-8 \|pages=57–66 \|s2cid=8437794 \|url=}}</ref> where log<sup>*</sup> denotes the [[iterated logarithm]]. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time.<ref>{{cite book \|first1=A. \|last1=De \|first2=C. \|last2=Saha \|first3=P. \|last3=Kurur \|first4=R. \|last4=Saptharishi \|chapter=Fast integer multiplication using modular arithmetic \|chapter-url= \|doi=10.1145/1374376.1374447 \|title=Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC) \|publisher= \|location= \|date=2008 \|isbn=978-1-60558-047-0 \|pages=499–506 \|url= \|arxiv=0801.1416\|s2cid=3264828 }}</ref> In context of the above material, what these latter authors have achieved is to find ''N'' much less than 2<sup>3''k''</sup> + 1, so that ''Z''/''NZ'' has a (2''m'')th root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.		In 2007 the [[asymptotic complexity]] of integer multiplication was improved by the Swiss mathematician [[Martin Fürer]] of Pennsylvania State University to <math display="inline">O(n \log n \cdot {2}^{\Theta(\log(n))})</math> using Fourier transforms over [[complex number]]s,<ref name="fürer_1">{{cite book \|first=M. \|last=Fürer \|chapter=Faster Integer Multiplication \|chapter-url=https://ivv5hpp.uni-muenster.de/u/cl/WS2007-8/mult.pdf \|doi=10.1145/1250790.1250800 \|title=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA \|publisher= \|location= \|date=2007 \|isbn=978-1-59593-631-8 \|pages=57–66 \|s2cid=8437794 \|url=}}</ref> where log<sup>*</sup> denotes the [[iterated logarithm]]. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time.<ref>{{cite book \|first1=A. \|last1=De \|first2=C. \|last2=Saha \|first3=P. \|last3=Kurur \|first4=R. \|last4=Saptharishi \|chapter=Fast integer multiplication using modular arithmetic \|chapter-url= \|doi=10.1145/1374376.1374447 \|title=Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC) \|publisher= \|location= \|date=2008 \|isbn=978-1-60558-047-0 \|pages=499–506 \|url= \|arxiv=0801.1416\|s2cid=3264828 }}</ref> In context of the above material, what these latter authors have achieved is to find ''N'' much less than 2<sup>3''k''</sup> + 1, so that ''Z''/''NZ'' has a (2''m'')th root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.

	In 2014, Harvey, [[Joris van der Hoeven]] and Lecerf<ref>{{cite journal		In 2014, Harvey, [[Joris van der Hoeven]] and Lecerf<ref>{{cite journal

Citation bot: Altered title. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Multiplication | #UCB_Category 33/42

2025-01-04T08:26:57Z

Altered title. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Multiplication | #UCB_Category 33/42

← Previous revision		Revision as of 08:26, 4 January 2025
Line 272:		Line 272:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= \| website=[[YouTube]]}}</ref>		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= The Genius Way Computers Multiply Big Numbers\| website=[[YouTube]]}}</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

Dominic3203: /* Computational complexity of multiplication */ Fixed typo

2025-01-04T08:25:31Z

Computational complexity of multiplication: Fixed typo

← Previous revision		Revision as of 08:25, 4 January 2025
Line 272:		Line 272:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/?v=AMl6EJHfUWo \| title=~~YouTube~~ \| website=[[YouTube]] }}</ref>		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= \| website=[[YouTube]]}}</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

Citation bot: Add: website, title. Changed bare reference to CS1/2. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Multiplication | #UCB_Category 8/42

2025-01-04T08:21:45Z

Add: website, title. Changed bare reference to CS1/2. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Multiplication | #UCB_Category 8/42

← Previous revision		Revision as of 08:21, 4 January 2025
Line 272:		Line 272:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>https://youtube.com/?v=AMl6EJHfUWo</ref>		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/?v=AMl6EJHfUWo \| title=YouTube \| website=[[YouTube]] }}</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

Dominic3203: /* Computational complexity of multiplication */ Added links

2025-01-04T08:17:03Z

Computational complexity of multiplication: Added links

← Previous revision		Revision as of 08:17, 4 January 2025
Line 272:		Line 272:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>https://youtube.com/?v=AMl6EJHfUWo</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

← Previous revision		Revision as of 11:16, 23 January 2025
Line 273:		Line 273:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= The Genius Way Computers Multiply Big Numbers\| website=[[YouTube]]}}</ref>		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= The Genius Way Computers Multiply Big Numbers\| website=[[YouTube]]\| date= 2 January 2025}}</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

← Previous revision		Revision as of 08:26, 4 January 2025
Line 272:		Line 272:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= \| website=[[YouTube]]}}</ref>		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= The Genius Way Computers Multiply Big Numbers\| website=[[YouTube]]}}</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

← Previous revision		Revision as of 08:25, 4 January 2025
Line 272:		Line 272:
	{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}		{{unsolved\|computer science\|What is the fastest algorithm for multiplication of two <math>n</math>-digit numbers?}}

	A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/?v=AMl6EJHfUWo \| title=~~YouTube~~ \| website=[[YouTube]] }}</ref>		A line of research in [[theoretical computer science]] is about the number of single-bit arithmetic operations necessary to multiply two <math>n</math>-bit integers. This is known as the [[computational complexity]] of multiplication. Usual algorithms done by hand have asymptotic complexity of <math>O(n^2)</math>, but in 1960 [[Anatoly Karatsuba]] discovered that better complexity was possible (with the [[Karatsuba algorithm]]).<ref>{{cite web \| url=https://youtube.com/watch?v=AMl6EJHfUWo \| title= \| website=[[YouTube]]}}</ref>

	Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.		Currently, the algorithm with the best computational complexity is a 2019 algorithm of [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]], which uses the strategies of using [[number-theoretic transform]]s introduced with the [[Schönhage–Strassen algorithm]] to multiply integers using only <math>O(n\log n)</math> operations.<ref>{{cite journal \| last1 = Harvey \| first1 = David \| last2 = van der Hoeven \| first2 = Joris \| author2-link = Joris van der Hoeven \| doi = 10.4007/annals.2021.193.2.4 \| issue = 2 \| journal = [[Annals of Mathematics]] \| mr = 4224716 \| pages = 563–617 \| series = Second Series \| title = Integer multiplication in time <math>O(n \log n)</math> \| volume = 193 \| year = 2021\| s2cid = 109934776 \| url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref> This is conjectured to be the best possible algorithm, but lower bounds of <math>\Omega(n\log n)</math> are not known.

← Previous revision		Revision as of 05:49, 20 January 2025
Line 363:		Line 363:
	{{Main\|Schönhage–Strassen algorithm}}		{{Main\|Schönhage–Strassen algorithm}}
	[[File:Integer multiplication by FFT.svg\|thumb\|350px\|Demonstration of multiplying 1234 × 5678 = 7006652 using fast Fourier transforms (FFTs). [[Number-theoretic transform]]s in the integers modulo 337 are used, selecting 85 as an 8th root of unity. Base 10 is used in place of base 2<sup>''w''</sup> for illustrative purposes.]]		[[File:Integer multiplication by FFT.svg\|thumb\|350px\|Demonstration of multiplying 1234 × 5678 = 7006652 using fast Fourier transforms (FFTs). [[Number-theoretic transform]]s in the integers modulo 337 are used, selecting 85 as an 8th root of unity. Base 10 is used in place of base 2<sup>''w''</sup> for illustrative purposes.]]


	Every number in base B, can be written as a polynomial:		Every number in base B, can be written as a polynomial:

	<math> X = \sum_{i=0}^N {x_iB^i} </math>		<math display="block"> X = \sum_{i=0}^N {x_iB^i} </math>

	Furthermore, multiplication of two numbers could be thought of as a product of two polynomials:		Furthermore, multiplication of two numbers could be thought of as a product of two polynomials:

	<math>XY = (\sum_{i=0}^N {x_iB^i})(\sum_{j=0}^N {y_iB^j}) </math>		<math display="block">XY = (\sum_{i=0}^N {x_iB^i})(\sum_{j=0}^N {y_iB^j}) </math>

	Because,for <math> B^k </math>: <math>c_k =\sum_{(i,j):i+j=k} {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}} </math>,		Because,for <math> B^k </math>: <math>c_k =\sum_{(i,j):i+j=k} {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}} </math>,
Line 378:		Line 377:
	By using fft (fast fourier transformation) with convolution rule, we can get		By using fft (fast fourier transformation) with convolution rule, we can get

	<math> \hat{f}(a * b) = \hat{f}(\sum_{i=0}^k {a_ib_{k-i}}) = \hat{f}(a)~~</math>~~ ~~● <math>~~ \hat{f}(b) </math>. That is; <math> C_k = a_k ~~</math> ● <math>~~ b_k </math>, where <math> C_k </math>		<math display="block"> \hat{f}(a * b) = \hat{f}(\sum_{i=0}^k {a_ib_{k-i}}) = \hat{f}(a) \bullet \hat{f}(b) </math>. That is; <math> C_k = a_k \bullet b_k </math>, where <math> C_k </math>
	is the corresponding coefficient in fourier space. This can also be written as: fft(a * b) = fft(a) ● fft(b).		is the corresponding coefficient in fourier space. This can also be written as: <math>\mathrm{fft}(a * b) = \mathrm{fft}(a) \bullet \mathrm{fft}(b)</math>.


Line 385:		Line 384:
	only consist of one unique term per coefficient:		only consist of one unique term per coefficient:

	<math> \hat{f}(x^n) = \left(\frac{i}{2\pi}\right)^n \delta^{(n)} </math> and		<math display="block"> \hat{f}(x^n) = \left(\frac{i}{2\pi}\right)^n \delta^{(n)} </math> and
	<math> \hat{f}(a\, X(\xi) + b\, Y(\xi)) = a\, \hat{X}(\xi) + b\, \hat{Y}(\xi)</math>		<math display="block"> \hat{f}(a\, X(\xi) + b\, Y(\xi)) = a\, \hat{X}(\xi) + b\, \hat{Y}(\xi)</math>


⚫	Convolution rule: <math> \hat{f}(X * Y) = \ \hat{f}(X) ~~</math>~~ ~~● <math>~~ \hat{f}(Y) </math>

		⚫	* Convolution rule: <math> \hat{f}(X * Y) = \ \hat{f}(X) \bullet \hat{f}(Y) </math>

	We have reduced our convolution problem		We have reduced our convolution problem
Line 396:		Line 393:

	By finding ifft (polynomial interpolation), for each <math>c_k </math>, one get the desired coefficients.		By finding ifft (polynomial interpolation), for each <math>c_k </math>, one get the desired coefficients.


	Algorithm uses divide and conquer strategy, to divide problem to subproblems.		Algorithm uses divide and conquer strategy, to divide problem to subproblems.