+
+\h{Paralelní násobení}
+
+Podobnì jako u~sèítání si vzpomeneme na~¹kolní algoritmus -- tentokráte v¹ak pro násobení.
+To fungovalo tak, ¾e~jsme si jedno ze~dvou binárních èísel na~vstupu (øíkejme mu tøeba $x$) $n$-krát posouvali. Tam kde pak byly v~èísle~$y$ jednièky, tak ty kopie $x$ jsme seèetli. Jinými slovy tedy násobení umíme pøevést na~nìjaké posuny (ty lze realizovat pouze \uv{pøedrátováním} -- nic nás nestojí), násobení jedním bitem (co¾ je $\&$) a~nakonec potøebujeme výsledných~$n$ èísel seèíst.
+\figure{skolni_scitani.eps}{©kolní sèítání.}{2in}
+
+Jak nyní seèíst $n$ $n$-bitových èísel..? Nabízí se vyu¾ít osvìdèený \uv{stromeèek} -- sèítat dvojice èísel, výsledky pak opìt po~dvojicích seèíst, a¾ na~konci vyjde jediný výsledek.
+\figure{stromecek.eps}{Stromeèek}{1.4in}
+
+Toto øe¹ení by v¹ak vedlo na~èasovou slo¾itost $\Theta (\log^2 n)$. To je dle na¹ich mìøítek
+jistì docela efektivní. Pøekvapivì to jde ale je¹tì lépe - toti¾ na~$\Theta (\log n)$. Této
+slo¾itosti dosáhneme malým trikem.
+
+Vymyslíme obvod, který na~vstupu dostane tøi èísla. Odpoví pak dvìma èísly
+takovými, ¾e budou mít stejný souèet jako pùvodní tøi èísla. Jinými slovy pomocí
+tohoto obvodu budeme umìt seètení tøí èísel pøevést na seètení dvou èísel.
+
+\figure{obvod.eps}{$x+y+z = p+q$}{0.3in}
+
+V¹imnìme si, ¾e~kdy¾ sèítáme tøi bity, mù¾e být pøenos do~vy¹¹ího øádu nula èi~jednièka. Vezmeme si tedy bity $x_i$, $y_i$, $z_i$ a~ty seèteme. To nám dá dvoubitový výsledek, pøièem¾ ni¾¹í bit z~tohoto výsledku po¹leme do~èísla~p, vy¹¹í do~èísla~q.
+
+\figure{obvod_real.eps}{Redukování sèítání}{1.2in}
+
+Toto zredukování sèítání nám nyní umo¾ní opìt stavit strom, by» o malièko slo¾itìj¹í.
+
+\figure{sl_stromecek.eps}{Slo¾itìj¹í stromeèek}{0.95in}
+
+V¹imnìme si, ¾e pokud jsme mìli na~zaèátku $n$ èísel, po~první redukci nám jich zbývá jen $2/3 n$ a~obecnì v~$k$-té hladiné $(2/3)^k n$. Znamená to, ¾e èísel nám ubývá exponenciálnì, tak¾e poèet hladin bude logaritmcký. Redukující obvod je pøi tom jen konstantnì hluboký, tak¾e celé redukování zvládneme v~èase $\Theta (\log n)$. Na~konci Slo¾itìj¹ího stromeèku pak máme umístìnou jednu obyèejnou sèítaèku, pøièem¾ dvì èísla takté¾ umíme seèíst v~logaritmickém èase.
+
+Celé sèítání $n$ $n$-bitových èísel nám tedy zabere $\Theta (\log n)$.
+
+Kdy¾ se nyní vrátíme k~násobení, zbývá nám vyøe¹it posouvání a~andování. Uvìdomme si, ¾e to je plnì paralelení a~zvládneme ho za~konstantu hladin. Celé násobení tedy zvládneme v~logaritmickém èase.
+