Multiplication algorithm - Revision history

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

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

Show changes