Násobení polynomů

Násobení dvou polynomů se dá naprogramovat třemi základními způsoby, které jsou progresivně obtížné na pochopení. Zde najdete přehled známých řešení, jejich naměřenou rychlost a celkové srovnání.

Naivní řešení

Násobení můžeme implementovat přesně podle definice. Je to nejspolehlivější způsob, který ale není zrovna efektivní. Výsledná složitost je pro velikost N obou polynomů O(N^2). Výsledný graf měření odpovídá očekávání - není co dodat.

Karatsuba

Algoritmus Karatsuba využívá toho, že pro výpočet (Ax + B)(C*x + D) nemusíme dělat čtyři násobení, ale pouze tři. Toto pravidlo se uplatňuje rekurzivně, a tak ušetříme mnoho operací. Stále jsme však uvězněni v polynomiální složitosti. Výsledná složitost je O(N^(log2(3))), to je cca N^(1.585). Skoky v grafu měření vysvětluje to, že implementace zaokrouhluje velikosti polynomů na nejbližší vyšší mocninu dvou - a tak pozorujeme skoky na 32768, 65536 atd.

Rychlá fourierova transformace (FFT)

Třetí možnost řešení je přes metodu Fourierovy transformace. Tato metoda vyžaduje slušnou znalost matematické analýzy, ale zato poskytuje uspokojující složitost O(N log N). Ze skoků v grafu opět viníme zaokrouhlování velikosti polynomů.

Výsledek

Srovnání nám ukazuje, že algoritmy jsou svým výkonem jednoznačně odlišeny. Je možné, že pro malé případy se vyplatí algoritmus naivní, ale od určité meze není lepší volby než FFT.

PS

Outliery všech měření přisuzuji nepřesnostem a tím, že testování probíhá na pc, které zároveň dělá další úkoly.