X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=5-addsort%2F5-addsort.tex;h=4e8bf813a900cff56979506bc2cb1d1b8908c2ca;hb=819fc7663b0e8e0d6a0d64fda03da05b5958e931;hp=57f618806af0f570278f3bc7472aef0308308af6;hpb=dc113436969c96f2a10e9c34da87054ac46edcd1;p=ads2.git

diff --git a/5-addsort/5-addsort.tex b/5-addsort/5-addsort.tex
index 57f6188..4e8bf81 100644
--- a/5-addsort/5-addsort.tex
+++ b/5-addsort/5-addsort.tex
@@ -4,7 +4,7 @@
 
 \h{Sèítání binárních èísel}
 
-Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice nazývejme
+Mìjme dvì èísla $x$ a $y$ zapsané ve~dvojkové soustavì. Jejich èíslice oznaème
 jako $x_{n-1}\ldots x_0$ a $y_{n-1}\ldots y_0$, kde $i$-tý øád má váhu $2^i$. Nyní budeme chtít tato èísla
 seèíst.
 
@@ -20,7 +20,7 @@ kde $z_i$ je $i$-t
 z~$(i-1)$-ního øádu do~$i$-tého. Pøenos pøitom nastane tehdy, pokud se~nám potkají
 dvì jednièky pod~sebou, nebo kdy¾ se~vyskytne alespoò jedna jednièka a~k~tomu
 pøenos z~ni¾¹ího øádu. Jinými slovy tehdy, kdy¾ ze~tøí xorovaných èíslic jsou alespoò
-dvì jednièky:
+dvì jednièky (pomocí obvodu pro Majoritu z minulé pøedná¹ky lehce zkonstruujeme):
 $$
 \eqalign{
 c_{0} &= 0 \cr
@@ -32,9 +32,11 @@ Takov
 Pokud bychom stavìli hradlovou sí» podle tohoto pøedpisu, byla by slo¾ená z~nìjakých
 podsítí (\uv{krabièek}), které budou mít na~vstupu $x_i$, $y_i$ a~$c_i$, jejich výstupem
 bude $z_i$ a~$c_{i+1}$. 
+
 \figure{hloupe_scitani.eps}{Sèítání ¹kolním algoritmem.}{1.5in}
+
 V¹imìme si, ¾e~ka¾dá krabièka závisí na~výstupu té pøedcházející. V¹echny
-krabièky tedy musí le¾et urèitì na~rùzných hladinách. Celkovì bychom museli pou¾ít
+krabièky tedy musí urèitì le¾et na~rùzných hladinách. Celkovì bychom museli pou¾ít
 $\Theta{(n)}$ hladin a~jeliko¾ je ka¾dá krabièka konsantnì velká, také $\Theta{(n)}$ hradel. To dává
 lineární èasovou i~prostorovou slo¾itost, èili oproti sekvenènímu algoritmu jsme si nepomohli.
 
@@ -45,41 +47,43 @@ Jedin
 aby~vydal souèet, musí poèkat na~to, a¾~dopoèítají v¹echny pøedcházející øády.
 Teprve pak se~toti¾ dozví pøenos. Kdybychom ov¹em pøenosy dokázali spoèítat
 nìjakým zpùsobem paralelnì, máme vyhráno. Jakmile známe v¹echny pøenosy, souèet
-u¾~zvládneme dopoèítat na~konstantnì mnoho hladin - tedy v~konstantním èase.
+u¾~zvládneme dopoèítat na~konstantnì mnoho hladin -- tedy v~konstantním èase.
 
 Podívejme se na~libovolný {\I blok} v~na¹em souètu. Tak budeme øíkat èíslùm
-$x_j\ldots x_i$ a $y_j\ldots y_i$ v~nìjakém intervalu indexù $\left<j,i\right>$. Pøenos $c_{j+1}$ vystupující z~tohoto bloku závisí mimo hodnot sèítancù u¾ pouze na~pøenosu $c_{i}$, který do bloku vstupuje.
+$x_j\ldots x_i$ a $y_j\ldots y_i$ v~nìjakém intervalu indexù $\left<i,j\right>$. Pøenos $c_{j+1}$ vystupující z~tohoto bloku závisí mimo hodnot sèítancù u¾ pouze na~pøenosu $c_{i}$, který do bloku vstupuje.
+
 \figure{blok_scitani.eps}{Blok souètu.}{3in}
+
 Z tohoto pohledu se mù¾eme na blok také dívat jako na nìjakou funkci, která
 dostane jednobitový vstup a vydá jednobitový výstup. To je nám pøíjemné, nebo» 
 takových funkcí existují jenom ètyøi typy:
 \numlist\ndotted
 \:$f(x) = 0$,  ~~~~(0)
 \:$f(x) = 1$,  ~~~~(1)
-\:$f(x) = x$,  ~~~~($<$)
+\:$f(x) = x$,  ~~~~($<$ -- kopírování)
 \:$f(x) = \neg{x}$.
 \endlist
 Jak se za~chvíli uká¾e, poslední pøípad, kdy by~nìjaký blok pøedával opaèný
 pøenos, ne¾ do~nìj vstupuje, navíc nikdy nemù¾e nastat. Pojïme si to rozmyslet.
 Jednobitové bloky se chovají velice jednodu¹e:
 
-\figure{bloky_1bit.eps}{Tabulka triviálních bitù.}{1.1in}
+\figure{bloky_1bit.eps}{Tabulka triviálních blokù.}{1.1in}
 
 Z prvního bloku evidentnì v¾dy vyleze 0, a»~do~nìj vstoupí jakýkoli pøenos.
 Poslední blok naopak sám o~sobì pøenos vytváøí, a»~ji¾ do~nìj vleze jakýkoliv.
-Bloky prostøední se chovají stejnì a~to tak, ¾e~samy o~sobì ¾ádný pøenos nevytvoøí,
+Bloky prostøední se chovají stejnì, a~to tak, ¾e~samy o~sobì ¾ádný pøenos nevytvoøí,
 ale~pokud do~nich nìjaký pøijde, tak~také odejde.
 
 Mìjme nyní nìjaký vìt¹í blok~$C$ slo¾ený ze~dvou men¹ích podblokù $A$ a~$B$, jejich¾
 chování u¾ známe. Z~toho mù¾eme odvodit, jak se chová celý blok:
 
-\figure{tabulka_skladani_bloku.eps}{Skládání chování blokù}{1.3in}
+\figure{tabulka_skladani_bloku.eps}{Skládání chování blokù.}{1.3in}
 
 Pokud vy¹¹í blok pøenos pohlcuje, pak a»~se u¾~ni¾¹í blok chová jakkoli, slo¾ení
 tìchto blokù musí v¾dy pohlcovat. V~prvním øádku tabulky jsou tudí¾ nuly. Analogicky,
 pokud vy¹¹í blok generuje pøenos, tak~ten ni¾¹í na~tom nic nezmìní. V~druhém
 øádku tabulky jsou tedy samé jednièky. Zajímavìj¹í pøípad nastává, pokud vy¹¹í blok
-kopíruje - tehdy zále¾í èistì na~chování ni¾¹ího bloku.
+kopíruje -- tehdy zále¾í èistì na~chování ni¾¹ího bloku.
 
 V¹imnìme si, ¾e~skládání chování blokù je vlastnì úplnì obyèejné skládání
 funkcí. Nyní bychom mohli prohlásit, ¾e~budeme poèítat nad~tøíprvkovou abecedou,
@@ -101,8 +105,8 @@ Zvolme si tedy k
 
 Tomu, ¾e blok kopíruje, odpovídá dvojice $p_i = 1$; $q_i = cokoliv$. V~ostatních
 pøípadech bude~$p_i$ nulové a~$q_i$ nám bude øíkat, co je na~výstupu pøíslu¹ného bloku.
-Jinými slovy $p_i = 0$ znamená funkce je konstanta, pøièem¾ $q_i$ øíká jaká, $p_i = 1$~znamená
-funkce je identita, a»~u¾~je $q_i$ cokoli.
+Jinými slovy $p_i = 0$ znamená, ¾e funkce je konstanta, pøièem¾ $q_i$ øíká jaká; naproti
+tomu $p_i = 1$~znamená, ¾e funkce je identita, a»~u¾~je $q_i$ cokoli.
 
 Pojïme si nyní ukázat, jak bude celé skládání blokù vypadat. Rozmysleme si,
 kdy je~$p$ celého dvojbloku jednièkové, tedy kdy celý dvojblok kopíruje. To nastane
@@ -113,7 +117,7 @@ Skl
 i~binárnì vý¹e uvedeným pøedpisem.
 
 Nyní si tedy mù¾eme dopøedu vypoèítat chování bloku velikosti jedna, poté
- z~nich skládáním blokù velikosti dva, dál velikosti ètyøi, osm, atd...
+ z~nich skládáním blokù velikosti dva, dál velikosti ètyøi, osm, atd \dots
 
 \h{Paralelní sèítání}
 
@@ -124,18 +128,18 @@ konstanta-kr
 
 \algo
 \:Spoèteme chování blokù velikosti~1. ($\O(1)$ hladin)
-\:Postupnì poèítáme chování blokù velikosti 2, 4, 8, ..., $2^k$.
+\:Postupnì poèítáme chování blokù \foot{myslíme \uv{pøirozenì zarovnané} bloky, tedy takové, jejich¾ poloha je násobkem velikosti} velikosti 2, 4, 8, ..., $2^k$. 
   ($\O(\log n)$ hladin, na~nich¾ se skládají bloky)
 \:$c_0 \leftarrow 0$ (pøenos do nejni¾¹ího øádu je v¾dy 0)
 \:Urèíme $c_n$ podle $c_0$ a chování (jediného) bloku velikosti~$n$.
 \:Postupnì dopoèítáme pøenosy na~hranicích dìlitelných $2^k$ \uv{zahu¹»ováním}:
-  jakmile víme $c_{2^k}$, mù¾eme dopoèítat $c_{2^k-2^{k-1}}$ podle
-  chování bloku $\left< 2^k-2^{k-1},2^k\right>$. ($\O(\log n)$ hladin,
+  jakmile víme $c_{2^k}$, mù¾eme dopoèítat $c_{2^k+2^{k-1}}$ podle
+  chování bloku $\left< 2^k+2^{k-1},2^k\right>$. ($\O(\log n)$ hladin,
   na~nich¾ se dosazuje)
-\:$\forall i: z_i = x_i \oplus y_i \oplus c_i$.
+\:Seèteme: $\forall i: z_i = x_i \oplus y_i \oplus c_i$.
 \endalgo
 
-\figure{1_9_deleni_bloku.eps}{Výpoèet pøenosu}{8cm}
+\figure{1_9_deleni_bloku.eps}{Výpoèet pøenosu.}{2.5in}
 
 Algoritmus pracuje v~èase $\O(\log n)$. Hradel je pou¾ito lineárnì: na~jednotlivých
 hladinách kroku~2 poèet hradel exponenciálnì klesá od~$n$ k~1, na~hladinách kroku~5
@@ -143,42 +147,46 @@ exponenci
 
 \h{Tøídìní}
 
+Nyní se podíváme na~druhý problém, a~to na~problém tøídìní. Ji¾ známe pomìrnì efektivní sekvenèní algoritmy, které dovedou tøídit v~prùmìrném èase $\O(n\log n)$. Byli bychom jistì rádi, kdybychom to zvládli je¹tì rychleji. Pojïme se podívat, zda by nám v tom nepomohlo problém paralelizovat -- tedy paralelní tøídìní.
+
+Budeme pøi tom pracovat na~výpoèetním modelu, kterému se øíká komparátorová sí». Ta je postavená z~hradel, kterým se øíká komparátory.
+
 \s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou
 komparátory.
 
-\figure{sortnet.0}{Komparátor.}{0.9in}
+\figure{sortnet.0}{Komparátor}{0.7in}
 
 Komparátor umí porovnat dvì hodnoty a~rozhodnout, která z~nich je vìt¹í
 a~která men¹í. Nevrací v¹ak booleovský výsledek jako bì¾né hradlo, ale má dva
 výstupy, pøièem¾ na~jednom vrátí men¹í ze~vstupních hodnot a~na~druhém vìt¹í.
 
-\>Výstupy komparátorù se nevìtví.
+Výstupy komparátorù se nevìtví. Nemù¾eme tedy jeden výstup \uv{rozdvojit} a~pøipojit ho na~dva vstupy. (Vìtvení by dokonce ani nemìlo smysl, proto¾e zatímco rozdvojit bychom mohli, slouèit u¾~ne. Pokud tedy chceme aby sí» mìla~$n$ vstupù~i~$n$ výstupù, rozdvojení stejnì nesmíme provést i kdybychom jej mìli povolené.)
 
 \s{Pøíklad:} {\sl Bubble sort}
 
-Obrázek Bubble\_1 ilustruje pou¾ití komparátorù pro tøídìní bubble sortem.
+Obrázek Bubble 1 ilustruje pou¾ití komparátorù pro tøídìní Bubble sortem.
 ©ipky pøedstavují jednotlivé komparátory. Výpoèet v¹ak je¹tì mù¾eme vylep¹it.
 
-\twofigures{sortnet.1}{Bubble\_1}{143pt}{sortnet.2}{Bubble\_2}{143pt}
+\twofigures{sortnet.1}{Bubble 1}{143pt}{sortnet.2}{Bubble 2}{143pt}
 
-Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble\_2).
+Sna¾íme se výpoèet co nejvíce paralelizovat (viz obrázek Bubble 2).
 Jak je vidìt, komparátory na sebe nemusejí èekat. Tím mù¾eme výpoèet urychlit a místo èasu $\Theta{(n^2)}$ docílit èasové slo¾itosti $\Theta{(n)}$. V obou pøípadech je zachován kvadratický prostor.
 
 \medskip
 \s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická}, právì tehdy, kdy¾
-pro nìjaké $x_k\in\{1, \dots, n-1\} $ platí, ¾e~v¹echny prvky pøed ním (vèetnì jeho samotného)
+pro nìjaké $x_k\in\{0, \dots, n-1\} $ platí, ¾e~v¹echny prvky pøed ním (vèetnì jeho samotného)
 tvoøí rostoucí poslopnost, kde¾to prvky stojící za~ním, tvoøí poslopnost klesající.
-Formálnì zaspáno musí platit, ¾e:
+Formálnì zapsáno musí platit, ¾e:
 $$x_0\leq x_1\leq \dots \leq x_k \geq x_{k+1}\geq\dots \geq x_{n-1}.$$
 
-\s{Definice:} Posloupnost je {\I bitonická}, právì kdy¾ $\exists~j\in \{1,\dots ,n-1\}$, pro
+\s{Definice:} Posloupnost je {\I bitonická}, právì kdy¾ $\exists~j\in \{0,\dots ,n-1\}$, pro
 které je rotace pùvodní posloupnosti o $j$ prvkù (posloupnost
 $x_j,x_{(j+1) \bmod n},\dots, x_{(j+n-1) \bmod n}$) èistì bitonická.
 
 \s{Definice:} {\I Separátor $S_n$} je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu
-(pro $i=0,\dots, {n/2}-1$) propojeny komparátorem. Minimum pak bude~$i$-tým,
+(pro $i=0,\dots, {n/2}-1$) propojeny komparátorem. Minimum se pak stane~$i$-tým,
 maximum  $(i+{n/2})$-ním prvkem výstupu.
-\figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = CMP(x_i, x_{i+{n/2}})$} {300pt}
+\figure{sortnet.3}{$(y_i, y_{i+{n/2}}) = \<CMP>(x_i, x_{i+{n/2}})$} {300pt}
 
 \s{Lemma:} Pokud vstup separátoru je bitonická posloupnost, pak výstup
 $y_0,\dots, y_{n-1}$ je posloupnost,  která splòuje:
@@ -189,13 +197,15 @@ bitonick
 (ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$.
 
 Separátor nám tedy jednu bitonickou posloupnost na~vstupu rozdìlí na~dvì
-bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první poslopnosti ($y_0,\dots, y_{n/2 -1}$)
+bitonické posloupnosti, pøièem¾ navíc ka¾dý prvek první posloupnosti ($y_0,\dots, y_{n/2 -1}$)
 je men¹í nebo roven prvkùm druhé posloupnosti.
 
 \>Ne¾ pøistoupíme k dùkazu lemmatu, uka¾me si, k èemu se nám bude hodit.
 
 
-\s{Definice:} {\I Bitonická tøídièka $B_n$} je obvod sestavený ze separátorù, který dostane-li na vstupu bitonickou posloupnost délky $n$ (BÚNO konstruujeme tøídièku pro $n=2^k$), vydá setøídìnou posloupnost délky $n$. 
+\s{Definice:} {\I Bitonická tøídièka $B_n$} je obvod sestavený ze separátorù, který dostane-li na vstupu bitonickou posloupnost délky $n$ (BÚNO konstruujeme tøídièku pro $n=2^k$), vydá setøídìnou zadanou posloupnost délky $n$. 
+
+Tøídièka dostane na~vstupu bitonickou posloupnost. Separátor~$S_n$ ji pak dle lemmatu rozdìlí na~dvì bitonické posloupnosti, kdy je ka¾dý prvek z~první posloupnosti men¹í ne¾ libovolný prvek z~druhé. Tyto poloviny pak dal¹í separátory rozdìlí na~ètvrtiny, ..., a¾~na~konci zbydou pouze jednoduché posloupnosti délky jedna (zjevnì setøídìné), které mezi sebou mají po¾adovanou nerovnost -- tedy ka¾dá posloupnost (nebo spí¹e prvek) nalevo je $\leq$ ne¾ prvek napravo od~nìj.
 
 \centerline{\epsfbox{sortnet.5}}
 
@@ -217,14 +227,12 @@ $B_{2n}$ set
 
 Nyní se pokusme odhadnout èasovou slo¾itost. Na¹e slévaèka, bude mít øádovì hloubku $\log n$.
 V ka¾dém bloku $M_n$ je navíc ukryta bitonická tøídièka s takté¾ logaritmickou hloubkou.
-Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^{2^k} + \dots + \log n$.
+Celková hloubka tedy bude $\log 2 + \log4 + \dots + \log 2^k + \dots + \log n$.
 Po seètení nakonec dostáváme výslednou èasovou slo¾itost $\Theta (\log^2 n)$.
 
 Dodejme je¹tì, ¾e existuje i~tøídicí algoritmus, kterému staèí jen ${\O}(\log n)$ hladin.
 Jeho multiplikativní konstanta je v¹ak pøíli¹ veliká, tak¾e je v~praxi nepou¾itelný.
 
-
-
 \h{Dùkaz Lemmatu:}
 (i) Nejprve nahlédneme, ¾e lemma platí, je-li vstupem èistì bitonická
 posloupnost. Dále BÚNO pøedpokládejme, ¾e vrchol posloupnosti je v~první polovinì (kdyby
@@ -232,8 +240,8 @@ byl vrchol za~polovinou, sta
 bychom stejný problém). Nyní si definujme $k := \min j: x_j > x_{j+n/2}$. (Pokud
 by~takové~$k$ neexistovalo, znamenalo by~to, ¾e vstupní posloupnost je monotónní.
 Separátor by tedy nic nedìlal a~pouze zkopíroval vstup na~výstup.) Nyní si v¹imìme,
-¾e jakmile jednou zaène palatit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude
-nám tato relace platit a¾~do~konce. Oznaème $x_m$ jako maximum vstupní posloupnosti.
+¾e jakmile jednou zaène platit, ¾e prvek na~levé stranì je men¹í ne¾ na~pravé, bude
+nám tato relace platit a¾~do~konce. Oznaème vrchol vstupní posloupnosti jako~$x_m$.
 Pak~$k$ bude jistì men¹í ne¾~$m$ a~$k+{n/2}$ bude vìt¹í ne¾~$m$. Mezi~$k$ a~$m$ je tedy
 vstupní posloupnost neklesající, mezi $k+{n/2}$ a~$n-1$ nerostoucí.
 
@@ -246,7 +254,7 @@ bitonickou posloupnost
 
 Dostaneme-li na vstupu obecnou bitonickou posloupnost, pøedstavíme si,
 ¾e je to èistì bitonická posloupnost zrotovaná o~$r$ prvkù (BÚNO
-doprava). Zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky
+doprava). Zjistíme, ¾e v~komparátorech se porovnávají tyté¾ prvky,
 jako kdyby zrotovaná nebyla. Výstup se od výstupu èistì bitonické
 posloupnosti zrotovaného o~$r$ bude li¹it prohozením úsekù $x_0$ a¾
 $x_{r-1}$ a~$x_{n/2}$ a¾ $x_{{n/2}+r-1}$. Obì výstupní
@@ -257,6 +265,41 @@ bitoni
 \qed
 
 \medskip
+
 \centerline{\epsfbox{sortnet.7}}
 
+
+\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.
+
 \bye