imported>LaundryPizza03: /* Further improvements */ Bigger than SSCG(2)

2026-03-21T07:53:11Z

Further improvements: Bigger than SSCG(2)

← Previous revision		Revision as of 07:53, 21 March 2026
Line 175:		Line 175:

	====Description====		====Description====
	~~On paper, write down in one~~ column the numbers ~~you get when you~~ repeatedly ~~halve~~ the multiplier, ignoring the remainder~~; in a~~ column beside it repeatedly ~~double~~ the multiplicand. ~~Cross~~ out each row ~~in which the last digit of~~ the first number is even, ~~and add~~ the remaining numbers in the second column to obtain the product.		One column contains the numbers that result from repeatedly halving the multiplier while ignoring the remainder. Another column beside it contains the results of repeatedly doubling the multiplicand. The product is evaluated by crossing out each row where the first number ends in an even digit, then summing up the remaining numbers in the second column in order to obtain the product.

	====Examples====		====Examples====
Line 231:		Line 231:

	: <math>		: <math>
	\frac{\left(x+y\right)^2}{4} - \frac{\left(x-y\right)^2}{4} =		\frac{\left(x+y\right)^2}{4} - \frac{\left(x-y\right)^2}{4} =
	~~\frac{1}{4}~~\left(\~~left(~~x~~^2+2xy~~+y^2\right) - \left(x^2-~~2xy+~~y~~^2\right)\right) =~~		\left(\frac{x+y}{2}\right)^2 - \left(\frac{x-y}{2}\right)^2 = xy
	~~\frac{1~~}{4}~~\left(4xy~~\right) = xy.
	</math>		</math>

Line 255:		Line 254:
	\|}		\|}

	~~If, for~~ example, ~~you wanted to multiply~~ 9 by 3, ~~you observe that~~ the sum and difference ~~are~~ 12 and 6 respectively. Looking both those values up on the table yields 36 and 9, the difference of which is 27, which is the product of 9 and 3.		For example, when multiplying 9 by 3, evaluating the sum and difference of those numbers yield 12 and 6 respectively. Looking both those values up on the table yields 36 and 9, the difference of which is 27, which is the product of 9 and 3.

	====History of quarter square multiplication====		====History of quarter square multiplication====
Line 275:		Line 274:
	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>		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 name="Harvey-vdHoeven">{{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.

	===Karatsuba multiplication===		===Karatsuba multiplication===
Line 397:		Line 396:
	\| year = 2016}}</ref> gave a new algorithm that achieves a running time of <math>O(n\log n \cdot 2^{3\log^* n})</math>, making explicit the implied constant in the <math>O(\log^* n)</math> exponent. They also proposed a variant of their algorithm which achieves <math>O(n\log n \cdot 2^{2\log^* n})</math> but whose validity relies on standard conjectures about the distribution of [[Mersenne prime]]s. In 2016, Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of [[Fermat primes]] that conjecturally achieves a complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>. This matches the 2015 conditional result of Harvey, van der Hoeven, and Lecerf but uses a different algorithm and relies on a different conjecture.<ref>{{cite journal \|first1=Svyatoslav \|last1=Covanov \|first2=Emmanuel \|last2=Thomé \|title=Fast Integer Multiplication Using Generalized Fermat Primes \|journal=[[Mathematics of Computation\|Math. Comp.]] \|volume=88 \|year=2019 \|issue=317 \|pages=1449–1477 \|doi=10.1090/mcom/3367 \|arxiv=1502.02800 \|s2cid=67790860 }}</ref> In 2018, Harvey and van der Hoeven used an approach based on the existence of short lattice vectors guaranteed by [[Minkowski's theorem]] to prove an unconditional complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>.<ref>{{cite journal \|first1=D. \|last1=Harvey \|first2=J. \|last2=van der Hoeven \|year=2019 \|title=Faster integer multiplication using short lattice vectors \|journal=The Open Book Series \|volume=2 \|pages=293–310 \|doi=10.2140/obs.2019.2.293 \|arxiv=1802.07932\|s2cid=3464567 }}</ref>		\| year = 2016}}</ref> gave a new algorithm that achieves a running time of <math>O(n\log n \cdot 2^{3\log^* n})</math>, making explicit the implied constant in the <math>O(\log^* n)</math> exponent. They also proposed a variant of their algorithm which achieves <math>O(n\log n \cdot 2^{2\log^* n})</math> but whose validity relies on standard conjectures about the distribution of [[Mersenne prime]]s. In 2016, Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of [[Fermat primes]] that conjecturally achieves a complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>. This matches the 2015 conditional result of Harvey, van der Hoeven, and Lecerf but uses a different algorithm and relies on a different conjecture.<ref>{{cite journal \|first1=Svyatoslav \|last1=Covanov \|first2=Emmanuel \|last2=Thomé \|title=Fast Integer Multiplication Using Generalized Fermat Primes \|journal=[[Mathematics of Computation\|Math. Comp.]] \|volume=88 \|year=2019 \|issue=317 \|pages=1449–1477 \|doi=10.1090/mcom/3367 \|arxiv=1502.02800 \|s2cid=67790860 }}</ref> In 2018, Harvey and van der Hoeven used an approach based on the existence of short lattice vectors guaranteed by [[Minkowski's theorem]] to prove an unconditional complexity bound of <math>O(n\log n \cdot 2^{2\log^* n})</math>.<ref>{{cite journal \|first1=D. \|last1=Harvey \|first2=J. \|last2=van der Hoeven \|year=2019 \|title=Faster integer multiplication using short lattice vectors \|journal=The Open Book Series \|volume=2 \|pages=293–310 \|doi=10.2140/obs.2019.2.293 \|arxiv=1802.07932\|s2cid=3464567 }}</ref>

	In March 2019, [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]] announced their discovery of an {{nowrap\|''O''(''n'' log ''n'')}} multiplication algorithm.<ref>{{Cite magazine\|url=https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/\|title=Mathematicians Discover the Perfect Way to Multiply\|last=Hartnett\|first=Kevin\|magazine=Quanta Magazine\|date=11 April 2019\|access-date=2019-05-03}}</ref> It was published in the ''[[Annals of Mathematics]]'' in 2021.<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~~> Because Schönhage and Strassen predicted that ''n'' log(''n'') is the "best possible" result, Harvey said: "...{{nbsp}}our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously."<ref>{{cite news \|last1=Gilbert \|first1=Lachlan \|title=Maths whiz solves 48-year-old multiplication problem \|url=https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem \|access-date=18 April 2019 \|publisher=UNSW \|date=4 April 2019}}</ref>		In March 2019, [[David Harvey (mathematician)\|David Harvey]] and [[Joris van der Hoeven]] announced their discovery of an {{nowrap\|''O''(''n'' log ''n'')}} multiplication algorithm.<ref>{{Cite magazine\|url=https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/\|title=Mathematicians Discover the Perfect Way to Multiply\|last=Hartnett\|first=Kevin\|magazine=Quanta Magazine\|date=11 April 2019\|access-date=2019-05-03}}</ref> It was published in the ''[[Annals of Mathematics]]'' in 2021.<ref name="Harvey-vdHoeven"/> Because Schönhage and Strassen predicted that ''n'' log(''n'') is the "best possible" result, Harvey said: "...{{nbsp}}our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously."<ref>{{cite news \|last1=Gilbert \|first1=Lachlan \|title=Maths whiz solves 48-year-old multiplication problem \|url=https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem \|access-date=18 April 2019 \|publisher=UNSW \|date=4 April 2019}}</ref> However, the new algorithm is highly impractical: it is faster than the Schönhage–Strassen algorithm only if the number of digits exceeds<ref name="Harvey-vdHoeven"/>
			:<math>\begin{aligned}
			2^{{1729}^{12}} &= 2^{713\,739\,807\,325\,663\,489\,766\,475\,852\,620\,783\,120\,641} \\
			&\approx 4.145331 \times 10^{214\,857\,091\,104\,455\,254\,035\,802\,532\,723\,729\,912\,717} \\
			&\approx 10^{2.148571 \times 10^{38}}.
			\end{aligned}</math>

	===Lower bounds===		===Lower bounds===

imported>Artoria2e5: /* Polynomial multiplication */ ~

2025-12-01T10:16:53Z

Polynomial multiplication: ~

← Previous revision		Revision as of 10:16, 1 December 2025
Line 374:		Line 374:
	<math display="block"> \hat{f}(XY) = \hat{f}(\sum_{i=0}^k {x_iy_{k-i}}) = \hat{f}(X)\cdot \hat{f}(Y). </math>		<math display="block"> \hat{f}(XY) = \hat{f}(\sum_{i=0}^k {x_iy_{k-i}}) = \hat{f}(X)\cdot \hat{f}(Y). </math>

	Therefore, the multiplication is reduced to a FFT, {{tmath\|N}} multiplications, and an inverse FFT. It results a [[time complexity]] of {{math\|''O''(''n'' log(''n'') log(log ''n''}})).		Therefore, the multiplication is reduced to a FFT, {{tmath\|N}} multiplications, and an inverse FFT. It results a [[time complexity]] of {{math\|''O''(''n'' log(''n'') log(log ''n''))}}.

	==== History ====		==== History ====
Line 453:		Line 453:
	t cwt qtr		t cwt qtr
	23 12 2		23 12 2
	47 x		47 ×
	————————————————		————————————————
	~~141 94~~ 94		1. Multiply everything by 47
	~~940 470~~		1081 564 94
	~~29 23~~
	————————————————		————————————————
	~~1110~~ 587 94		2a. Carry qtr & add to cwt (94 = 23 × 4 + 2)
			(564) <s>94</s>
			23 2
			—————
			587 2
			2b. Carry cwt & add to t (587 = 29 × 20 + 7)
			(1081) <s>587</s> 2
			29 7
	————————————————		————————————————
			3. Final add
	1110 7 2		1110 7 2
	<nowiki>=================</nowiki> Answer: 1110 ton 7 cwt 2 qtr		<nowiki>=================</nowiki> Answer: 1110 ton 7 cwt 2 qtr

	First multiply the quarters by 47, the result 94 is written into the first workspace. Next, multiply cwt 1247 = (2 + 10)47 but don't add up the partial results (94, 470) yet. Likewise multiply 23 by 47 yielding (141, 940). The quarters column is totaled and the result placed in the second workspace (a trivial move in this case). 94 quarters is 23 cwt and 2 qtr, so place the 2 in the answer and put the 23 in the next column left. Now add up the three entries in the cwt column giving 587. This is 29 t 7 cwt, so write the 7 into the answer and the 29 in the column to the left. Now add up the tons column. There is no adjustment to make, so the result is just copied down.

	The same layout and methods can be used for any traditional measurements and non-decimal currencies such as the old British [[£sd]] system.		The same layout and methods can be used for any traditional measurements and non-decimal currencies such as the old British [[£sd]] system.

imported>Akshat251: /* Algorithms for multiplying by hand */ Added links

2025-11-19T01:53:09Z

Algorithms for multiplying by hand: Added links

Show changes

imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-06-19T23:29:24Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 23:29, 19 June 2025
Line 400:		Line 400:
	==== History ====		==== History ====

	The algorithm was invented by [[Volker Strassen\|Strassen]] (1968). It was made practical and theoretical guarantees were provided in 1971 by [[Arnold Schönhage\|Schönhage]] and Strassen resulting in the [[Schönhage–Strassen algorithm]].<ref name="schönhage">{{cite journal \|first1=A. \|last1=Schönhage \|first2=V. \|last2=Strassen \|title=Schnelle Multiplikation großer Zahlen \|journal=Computing \|volume=7 \|issue= 3–4\|pages=281–292 \|date=1971 \|doi=10.1007/BF02242355 \|s2cid=9738629 \|url=https://link.springer.com/article/10.1007/BF02242355}}</ref>		The algorithm was invented by [[Volker Strassen\|Strassen]] (1968). It was made practical and theoretical guarantees were provided in 1971 by [[Arnold Schönhage\|Schönhage]] and Strassen resulting in the [[Schönhage–Strassen algorithm]].<ref name="schönhage">{{cite journal \|first1=A. \|last1=Schönhage \|first2=V. \|last2=Strassen \|title=Schnelle Multiplikation großer Zahlen \|journal=Computing \|volume=7 \|issue= 3–4\|pages=281–292 \|date=1971 \|doi=10.1007/BF02242355 \|s2cid=9738629 \|url=https://link.springer.com/article/10.1007/BF02242355\|url-access=subscription }}</ref>

	=== Further improvements ===		=== Further improvements ===

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

2025-01-25T22:32:40Z