Násobení Toom – Cook - Toom–Cook multiplication

Toom – Cook , někdy známý jako Toom-3 , pojmenovaný po Andrei Toomovi , který představil nový algoritmus s jeho nízkou složitostí, a Stephenovi Cookovi , který jeho popis vyčistil, je multiplikační algoritmus pro velká celá čísla.

Vzhledem ke dvěma velkým celým číslům a a b rozdělí Toom – Cook a a b na k menších částí, každá o délce l , a provede operace s částmi. Jak k roste, lze kombinovat mnoho z multiplikačních dílčích operací, čímž se snižuje celková složitost algoritmu. Sub-operace násobení pak mohou být vypočítány rekurzivně pomocí Toom – Cookova násobení znovu atd. Ačkoli jsou výrazy „Toom-3“ a „Toom – Cook“ někdy zaměnitelně nesprávně používány, Toom-3 je pouze jednou instancí algoritmu Toom – Cook, kde k = 3.

Toom-3 redukuje 9 násobení na 5 a běží v Θ ( n ^{log (5) / log (3)} ) ≈ ≈ ( n ^1,46 ). Obecně platí, že Toom- K probíhá v t Vstup ( c ( k ) n ^e ) , kde e = log (2 k - 1) / log ( k ) , n ^e je čas strávený na dílčích násobení, a c je čas utracené za sčítání a násobení malými konstantami. Karatsuba algoritmus je zvláštní případ Toom-Cook, kde se počet rozdělena do dvou menších. Snižuje 4 násobení na 3, a proto pracuje při Θ ( n ^{log (3) / log (2)} ) ≈ Θ ( n ^1,58 ). Obyčejné dlouhé násobení je ekvivalentní Toom-1, se složitostí Θ ( n ² ).

Ačkoli exponent e lze libovolně nastavit na 1 zvětšením k , funkce c bohužel roste velmi rychle. Míra růstu schémat Toom – Cook na smíšené úrovni byla v roce 2005 stále otevřeným výzkumným problémem. Implementace popsaná Donaldem Knuthem dosahuje časové složitosti $Θ (n 2 \sqrt 2 log n log n)$ .

Díky své režii je Toom – Cook pomalejší než dlouhé množení s malým počtem, a proto se obvykle používá pro násobení střední velikosti, před asymptoticky rychlejším Schönhage – Strassenovým algoritmem (se složitostí Θ ( n log n log log n ) ) stane se praktickým.

Toom poprvé popsal tento algoritmus v roce 1963 a Cook ve své disertační práci v roce 1966 publikoval vylepšený (asymptoticky ekvivalentní) algoritmus.

Detaily

Tato část pojednává přesně o tom, jak provést Toom- k pro jakoukoli danou hodnotu k , a je zjednodušením popisu polynomického násobení Toom – Cook popsaného Marcem Bodratem. Algoritmus má pět hlavních kroků:

V typické implementaci velkého celého čísla je každé celé číslo představováno jako posloupnost číslic v poziční notaci , přičemž základna nebo radix je nastavena na nějakou (obvykle velkou) hodnotu b ; v tomto příkladu používáme b = 10 000, takže každá číslice odpovídá skupině čtyř desetinných míst (v počítačové implementaci by b byla místo toho mocnina 2). Řekněme, že dvě celá čísla, která se násobí, jsou:

m	=	12	3456	7890	1234	5678	9012
n	=	9	8765	4321	9876	5432	1098.

Ty jsou mnohem menší, než by byly normálně zpracovány pomocí Toom – Cook (násobení na základní škole by bylo rychlejší), ale budou sloužit k ilustraci algoritmu.

Rozdělení

Prvním krokem je výběr základny B = b ⁱ , takže počet číslic obou m a n v základně B je nanejvýš k (např. 3 v Toom-3). Typickou volbu pro i dává:

{\ displaystyle i = \ max \ left \ {\ left \ lfloor {\ frac {\ left \ lfloor \ log _ {b} m \ right \ rfloor} {k}} \ right \ rfloor, \ left \ lfloor {\ frac {\ left \ lfloor \ log _ {b} n \ right \ rfloor} {k}} \ right \ rfloor \ right \} + 1.}

V našem příkladu budeme dělat Toom-3, takže zvolíme B = b ² = ¹⁰⁸ . Poté oddělíme m a n do jejich základních B číslic m _i , n _i :

{\ displaystyle {\ begin {aligned} m_ {2} & {} = 123456 \\ m_ {1} & {} = 78901234 \\ m_ {0} & {} = 56789012 \\ n_ {2} & {} = 98765 \\ n_ {1} & {} = 43219876 \\ n_ {0} & {} = 54321098 \ end {zarovnáno}}}

Pak používáme tyto číslice jako koeficientů stupeň- ( k - 1) polynomy p a q , s vlastností, že p ( B ) = m a q ( B ) = n :

{\ displaystyle p (x) = m_ {2} x ^ {2} + m_ {1} x + m_ {0} = 123456x ^ {2} + 78901234x + 56789012 \,}

{\ displaystyle q (x) = n_ {2} x ^ {2} + n_ {1} x + n_ {0} = 98765x ^ {2} + 43219876x + 54321098 \,}

Účelem definování těchto polynomů je, že pokud můžeme vypočítat jejich součin r ( x ) = p ( x ) q ( x ) , naše odpověď bude r ( B ) = m × n .

V případě, že násobená čísla mají různé velikosti, je užitečné použít různé hodnoty k pro m a n , které budeme nazývat k _m a k _n . Například algoritmus „Toom-2.5“ odkazuje na Toom – Cook s k _m = 3 a k _n = 2. V tomto případě je i v B = b ⁱ obvykle zvoleno:

{\ displaystyle i = \ max \ left \ {\ left \ lfloor {\ frac {\ left \ lceil \ log _ {b} m \ right \ rceil} {k_ {m}}} \ right \ rfloor, \ left \ lfloor {\ frac {\ left \ lceil \ log _ {b} n \ right \ rceil} {k_ {n}}} \ right \ rfloor \ right \}.}

Hodnocení

Přístup Toom – Cook k výpočtu polynomiálního produktu p ( x ) q ( x ) je běžně používaný. Všimněte si, že polynom stupně d je jednoznačně určen d + 1 body (například přímka - polynom stupně prvního je určen dvěma body). Cílem je vyhodnotit p (·) a q (·) v různých bodech. Poté vynásobte jejich hodnoty v těchto bodech, abyste získali body na polynomu součinu. Nakonec interpolujte, abyste našli jeho koeficienty.

Protože deg ( pq ) = deg ( p ) + deg ( q ) , budeme potřebovat deg ( p ) + deg ( q ) + 1 = k _m + k _n - 1 body k určení konečného výsledku. Říkejte tomu d . V případě Toom-3, d = 5. Algoritmus bude fungovat bez ohledu na to, jaké body jsou zvoleny (až na několik malých výjimek viz požadavek na invertibilitu matice v Interpolaci ), ale v zájmu zjednodušení algoritmu je lepší zvolit malý celočíselné hodnoty jako 0, 1, -1 a -2.

Jedna neobvyklá bodová hodnota, která se často používá, je nekonečno, napsané ∞ nebo 1/0. „Vyhodnocení“ polynomu p v nekonečnu ve skutečnosti znamená vzít limit p ( x ) / x ^{deg p,} protože x jde do nekonečna. V důsledku toho je p (∞) vždy hodnota jeho koeficientu nejvyššího stupně (v příkladu výše koeficient m ₂ ).

V našem příkladu Toom-3 použijeme body 0, 1, −1, −2 a ∞. Tyto možnosti zjednodušují hodnocení a vytvářejí vzorce:

{\ displaystyle {\ begin {array} {lrlrl} p (0) & = & m_ {0} + m_ {1} (0) + m_ {2} (0) ^ {2} & = & m_ {0} \\ p (1) & = & m_ {0} + m_ {1} (1) + m_ {2} (1) ^ {2} & = & m_ {0} + m_ {1} + m_ {2} \\ p ( -1) & = & m_ {0} + m_ {1} (- 1) + m_ {2} (- 1) ^ {2} & = & m_ {0} -m_ {1} + m_ {2} \\ p (-2) & = & m_ {0} + m_ {1} (- 2) + m_ {2} (- 2) ^ {2} & = & m_ {0} -2 m_ {1} + 4 m_ {2} \\ p (\ infty) & = & m_ {2} && \ end {pole}}}

a analogicky pro q . V našem příkladu jsou hodnoty, které dostaneme:

p (0)	=	m ₀	=	56789012	=	56789012
p (1)	=	m ₀ + m ₁ + m ₂	=	56789012 + 78901234 + 123456	=	135813702
p (-1)	=	m ₀ - m ₁ + m ₂	=	56789012 - 78901234 + 123456	=	-21988766
p (-2)	=	m ₀ - 2 m ₁ + 4 m ₂	=	56789012 - 2 × 78901234 + 4 × 123456	=	-100519632
p (∞)	=	m ₂	=	123456	=	123456
q (0)	=	n ₀	=	54321098	=	54321098
q (1)	=	n ₀ + n ₁ + n ₂	=	54321098 + 43219876 + 98765	=	97639739
q (-1)	=	n ₀ - n ₁ + n ₂	=	54321098 - 43219876 + 98765	=	11199987
q (-2)	=	n ₀ - 2 n ₁ + 4 n ₂	=	54321098 - 2 × 43219876 + 4 × 98765	=	-31723594
q (∞)	=	n ₂	=	98765	=	98765.

Jak je znázorněno, mohou být tyto hodnoty záporné.

Pro účely pozdějšího vysvětlení bude užitečné nahlížet na tento proces hodnocení jako na multiplikaci matice-vektor, kde každý řádek matice obsahuje mocniny jednoho z hodnotících bodů a vektor obsahuje koeficienty polynomu:

{\ displaystyle \ left ({\ begin {matrix} p (0) \\ p (1) \\ p (-1) \\ p (-2) \\ p (\ infty) \ end {matrix}} \) right) = \ left ({\ begin {matrix} 0 ^ {0} & 0 ^ {1} & 0 ^ {2} \\ 1 ^ {0} & 1 ^ {1} & 1 ^ {2} \\ (- 1) ^ {0} & (- 1) ^ {1} & (- 1) ^ {2} \\ (- 2) ^ {0} & (- 2) ^ {1} & (- 2) ^ {2} \\ 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ begin {matrix} m_ {0} \\ m_ {1} \\ m_ {2} \ end {matrix}} \ right) = \ left ( {\ begin {matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & -2 & 4 \\ 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ begin {matrix} m_ {0} \\ m_ {1 } \\ m_ {2} \ end {matrix}} \ right).}

Rozměry matice jsou d o k _m pro p a d o k _n pro q . Řádek pro nekonečno je vždy nula, kromě 1 v posledním sloupci.

Rychlejší vyhodnocení

Vícebodové vyhodnocení lze získat rychleji než u výše uvedených vzorců. Počet základních operací (sčítání / odčítání) lze snížit. Sekvence daná Bodrato pro Toom-3, provedená zde přes první operand (polynom p ) běžícího příkladu, je následující:

p ₀	←	m ₀ + m ₂	=	56789012 + 123456	=	56912468
p (0)	=	m ₀	=	56789012	=	56789012
p (1)	=	p ₀ + m ₁	=	56912468 + 78901234	=	135813702
p (-1)	=	p ₀ - m ₁	=	56912468 - 78901234	=	-21988766
p (-2)	=	( p (-1) + m ₂ ) × 2 - m ₀	=	(- 21988766 + 123456) × 2 - 56789012	=	- 100519632
p (∞)	=	m ₂	=	123456	=	123456.

Tato sekvence vyžaduje pět operací sčítání / odčítání, o jednu méně než přímé vyhodnocení. Navíc bylo uloženo násobení 4 při výpočtu p (-2).

Bodové násobení

Na rozdíl od násobení polynomů p (·) a q (·), vynásobení vyhodnocených hodnot p ( a ) a q ( a ) zahrnuje pouze vynásobení celých čísel - menší instance původního problému. Rekurzivně vyvoláme náš postup násobení, abychom každou dvojici hodnocených bodů vynásobili. V praktických implementacích, jak se operandy zmenšují, se algoritmus přepne na dlouhé násobení učebnice . Nechť r je polynom produktu, v našem příkladu máme:

r (0)	=	p (0) q (0)	=	56789012 × 54321098	=	3084841486175176
r (1)	=	p (1) q (1)	=	135813702 × 97639739	=	13260814415903778
r (-1)	=	p (-1) q (-1)	=	−21988766 × 11199987	=	-246273893346042
r (-2)	=	p (-2) q (-2)	=	−100519632 × −31723594	=	3188843994597408
r (∞)	=	p (∞) q (∞)	=	123456 × 98765	=	12193131840.

Jak je znázorněno, mohou být také negativní. Pro dostatečně velká čísla je to nejdražší krok, jediný krok, který není lineární ve velikostech m a n .

Interpolace

Toto je nejsložitější krok, zadní část hodnotícího kroku: vzhledem k našim bodům d na součinovém polynomu r (·) musíme určit jeho koeficienty. Jinými slovy, chceme vyřešit tuto maticovou rovnici pro vektor na pravé straně:

{\ displaystyle {\ začátek {zarovnáno} \ vlevo ({\ začátek {matice} r (0) \\ r (1) \\ r (-1) \\ r (-2) \\ r (\ infty) \ end {matrix}} \ right) & {} = \ left ({\ begin {matrix} 0 ^ {0} & 0 ^ {1} & 0 ^ {2} & 0 ^ {3} & 0 ^ {4} \\ 1 ^ {0} & 1 ^ {1} & 1 ^ {2} & 1 ^ {3} & 1 ^ {4} \\ (- 1) ^ {0} & (- 1) ^ {1} & (- 1) ^ {2 } & (- 1) ^ {3} & (- 1) ^ {4} \\ (- 2) ^ {0} & (- 2) ^ {1} & (- 2) ^ {2} & (- 2) ^ {3} & (- 2) ^ {4} \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ begin {matrix} r_ {0} \\ r_ {1} \\ r_ { 2} \\ r_ {3} \\ r_ {4} \ end {matrix}} \ right) \\ & {} = \ left ({\ begin {matrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \ \ 1 & -2 & 4 & -8 & 16 \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ begin {matrix} r_ {0} \\ r_ {1} \\ r_ {2} \\ r_ {3} \ \ r_ {4} \ end {matrix}} \ right). \ end {zarovnáno}}}

Tato matice je konstruována stejným způsobem jako matice v kroku hodnocení, kromě toho, že je to d × d . Tuto rovnici bychom mohli vyřešit technikou, jako je Gaussova eliminace , ale je to příliš drahé. Místo toho použijeme skutečnost, že za předpokladu, že byly vyhodnocovací body zvoleny vhodně, je tato matice invertibilní (viz také Vandermondeova matice ), a tak:

{\ displaystyle {\ begin {zarovnáno} \ left ({\ begin {matrix} r_ {0} \\ r_ {1} \\ r_ {2} \\ r_ {3} \\ r_ {4} \ end {matice }} \ right) & {} = \ left ({\ begin {matrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & -2 & 4 & -8 & 16 \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ right) ^ { -1} \ left ({\ begin {matrix} r (0) \\ r (1) \\ r (-1) \\ r (-2) \\ r (\ infty) \ end {matrix}} \) vpravo) \\ & {} = \ doleva ({\ begin {matrix} 1 & 0 & 0 & 0 & 0 \\ {\ tfrac {1} {2}} & {\ tfrac {1} {3}} & - 1 & {\ tfrac {1} {6}} & - 2 \\ - 1 & {\ tfrac {1} {2}} & {\ tfrac {1} {2}} & 0 & -1 \\ - {\ tfrac {1} {2}} & { \ tfrac {1} {6}} & {\ tfrac {1} {2}} & - {\ tfrac {1} {6}} & 2 \\ 0 & 0 & 0 & 0 & 1 \ end {matrix}} \ right) \ left ({\ začátek {matrix} r (0) \\ r (1) \\ r (-1) \\ r (-2) \\ r (\ infty) \ end {matrix}} \ right). \ end {zarovnáno} }}

Zbývá jen spočítat tento produkt matice-vektor. I když matice obsahuje zlomky, výsledné koeficienty budou celá čísla - takže to lze provést pomocí celočíselné aritmetiky, pouze sčítáním, odčítáním a násobením / dělením malými konstantami. Obtížnou výzvou designu v Toom – Cook je najít efektivní posloupnost operací pro výpočet tohoto produktu; jedna sekvence daná Bodrato pro Toom-3 je následující, zde provedená přes běžící příklad:

r ₀	←	r (0)	=	3084841486175176
r ₄	←	r (∞)	=	12193131840
r ₃	←	( r (-2) - r (1)) / 3	=	(3188843994597408 - 13260814415903778) / 3
			=	−3357323473768790
r ₁	←	( r (1) - r (-1)) / 2	=	(13260814415903778 - (-246273893346042)) / 2
			=	6753544154624910
r ₂	←	r (-1) - r (0)	=	- 246273893346042 - 3084841486175176
			=	-3331115379521218
r ₃	←	( r ₂ - r ₃ ) / 2 + 2 r (∞)	=	(−3331115379521218 - (−3357323473768790)) / 2 + 2 × 12193131840
			=	13128433387466
r ₂	←	r ₂ + r ₁ - r ₄	=	−3331115379521218 + 6753544154624910 - 12193131840
			=	3422416581971852
r ₁	←	r ₁ - r ₃	=	6753544154624910-13128433387466
			=	6740415721237444.

Nyní známe náš produktový polynom r :

{\ displaystyle {\ begin {array} {rrr} r (x) = & {} & 3084841486175176 \\ & + & 6740415721237444x \\ & + & 3422416581971852x ^ {2} \\ & + a 13128433387466x ^ {3} \\ & + & 12193131840x ^ {4} \ end {pole}}}

Pokud bychom používali různé k _m , k _n nebo hodnotící body, matice a tak by se naše interpolační strategie změnila; ale to nezávisí na vstupech, a proto může být pevně zakódováno pro libovolnou danou sadu parametrů.

Rekompozice

Nakonec vyhodnotíme r (B), abychom získali naši konečnou odpověď. To je jednoduché, protože B je mocnina b, takže násobení mocninami B jsou všechny posuny o celý počet číslic v základně b . V běžícím příkladu b = 10 ⁴ a B = b ² = 10 ⁸ .

								3084	8414	8617	5176
						6740	4157	2123	7444
				3422	4165	8197	1852
		13	1284	3338	7466
+	121	9313	1840

	121	9326	3124	6761	1632	4937	6009	5208	5858	8617	5176

A toto je ve skutečnosti produkt 1234567890123456789012 a 987654321987654321098.

Interpolační matice pro různé k

Zde uvádíme společné interpolační matice pro několik různých společných malých hodnot k _m a k _n .

Toom-1

Toom-1 ( k _m = k _n = 1) vyžaduje 1 vyhodnocovací bod, který je zde zvolen jako 0. Degeneruje se na dlouhé násobení s interpolační maticí matice identity:

{\ displaystyle \ left ({\ begin {matrix} 1 \ end {matrix}} \ right) ^ {- 1} = \ left ({\ begin {matrix} 1 \ end {matrix}} \ right).}

Toom-1.5

Toom-1,5 ( k _m = 2, k _n = 1) vyžaduje 2 body hodnocení, zde zvolené jako 0 a ∞. Jeho interpolační maticí je pak matice identity:

{\ displaystyle \ left ({\ begin {matrix} 1 & 0 \\ 0 & 1 \ end {matrix}} \ right) ^ {- 1} = \ left ({\ begin {matrix} 1 & 0 \\ 0 & 1 \ end {matrix}} \že jo).}

To také degeneruje do dlouhého násobení: oba koeficienty jednoho faktoru jsou vynásobeny jediným koeficientem druhého faktoru.

Toom-2

Toom-2 ( k _m = 2, k _n = 2) vyžaduje 3 hodnotící body, zde zvolené jako 0, 1 a ∞. Je to stejné jako s množením Karatsuba s interpolační maticí:

{\ displaystyle \ left ({\ begin {matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \ end {matrix}} \ right) ^ {- 1} = \ left ({\ begin {matrix} 1 & 0 & 0 \\ - 1 & 1 & -1 \\ 0 & 0 & 1 \ end {matrix}} \ right).}

Toom-2.5

Toom-2.5 ( k _m = 3, k _n = 2) vyžaduje 4 hodnotící body, zde zvolené jako 0, 1, −1 a ∞. Pak má interpolační matici:

{\ displaystyle \ left ({\ begin {matrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 0 & 0 & 0 & 1 \ end {matrix}} \ right) ^ {- 1} = \ left ({\ begin {matrix} 1 & 0 & 0 & 0 \\ 0 & {\ tfrac {1} {2}} & - {\ tfrac {1} {2}} & - 1 \\ - 1 & {\ tfrac {1} {2}} & {\ tfrac {1} {2}} & 0 \\ 0 & 0 & 0 & 1 \ end {matrix}} \ right).}

Poznámky

^ ^a ^b Knuth, str. 296
^ Crandall a Pomerance, str. 474
^ Crandall a Pomerance, str. 536
^ Knuth, str. 302
^ Pozitivní výsledky , kapitola III Stephena A. Cooka: O minimální době výpočtu funkcí .
^ ^a ^b ^c Marco Bodrato. Směrem k optimálnímu násobení Toom – Cook pro jednorozměrné a vícerozměrné polynomy v charakteristice 2 a 0. V řízení WAIFI'07 , svazek 4547 LNCS, strany 116–133. Autorský web 21. – 22. Června 2007.

Reference

D. Knuth. The Art of Computer Programming , svazek 2. Třetí vydání, Addison-Wesley, 1997. Oddíl 4.3.3.A: Digitální metody, str. 294.
R. Crandall a C. Pomerance. Prvočísla - výpočetní perspektiva . Druhé vydání, Springer, 2005. Oddíl 9.5.1: Metody Karatsuba a Toom – Cook, str. 473.
M. Bodrato. Směrem Optimal Toom-Cook násobení ... . V WAIFI'07, Springer, 2007.

externí odkazy

Toom – Cook 3-way multiplication z dokumentace GMP

[Knuth,_p._296-1] Knuth, str. 296

[2] Crandall a Pomerance, str. 474

[3] Crandall a Pomerance, str. 536

[4] Knuth, str. 302

[5] Pozitivní výsledky , kapitola III Stephena A. Cooka: O minimální době výpočtu funkcí .

[Bodrato2007-6] Marco Bodrato. Směrem k optimálnímu násobení Toom – Cook pro jednorozměrné a vícerozměrné polynomy v charakteristice 2 a 0. V řízení WAIFI'07 , svazek 4547 LNCS, strany 116–133. Autorský web 21. – 22. Června 2007.

Languages

In other projects