7-ram/7-ram.tex

   1 \input ../sgr.tex
   2
   3 % Makra pro bitove operace
   4 \def\rack#1#2{\setbox0=\hbox{#1}\hbox to \wd0{#2}}
   5
   6 \newdimen\slotwd
   7 \def\slot#1{\hbox to \slotwd{\hfil #1\hfil}}
   8 \def\[#1]{\slot{$#1$}}
   9
  10 \def\0{{\bf 0}}
  11 \def\1{{\bf 1}}
  12 \def\9{\rack{\0}{\hss$\cdot$\hss}}
  13 \def\opnot{\mathop{\lnot}}
  14 \def\shl{\mathop{<\!<}}
  15 \def\shr{\mathop{>\!>}}
  16 \def\opdiv{\mathop{/}}
  17 \def\opmod{\mathop{\%}}
  18
  19 \def\alik#1{%
  20 \medskip
  21 \halign{\hskip 0.2\hsize\hfil $ ##$&\hbox to 0.6\hsize{${}##$ \hss}\cr
  22 #1}
  23 \medskip
  24 }
  25
  26 \prednaska{7}{Výpoèetní modely}{}
  27
  28 Kdy¾ jsme v~pøede¹lých kapitolách studovali algoritmy, nezabývali jsme se tím,
  29 v~jakém pøesnì výpoèetním modelu pracujeme. Konstrukce, které jsme pou¾ívali,
  30 toti¾ fungovaly ve~v¹ech obvyklých modelech a mìly tam stejnou èasovou
  31 i prostorovu slo¾itost. Ne~v¾dy tomu tak je, tak¾e se výpoèetním modelùm
  32 podívejme na~zoubek trochu blí¾e.
  33
  34 \h{Druhy výpoèetních modelù}
  35
  36 Obvykle se pou¾ívají následující dva modely, které se li¹í zejména v~tom,
  37 zda je mo¾né pamì» indexovat v~konstantním èase èi nikoliv.
  38
  39 \s{Pointer Machine (PM)} \cite{benamram95what} pracuje se dvìma typy dat: {\I èísly} v~pevnì omezeném
  40 rozsahu a {\I pointery,} které slou¾í k~odkazování na~data ulo¾ená v~pamìti.
  41 Pamì» tohoto modelu je slo¾ená z pevného poètu registrù na~èísla a
  42 na~pointery a z~neomezeného poètu {\I krabièek.} Ka¾dá krabièka má pevný
  43 poèet polo¾ek na èísla a pointery. Na~krabièku se lze odkázat pouze
  44 pointerem.
  45
  46 Aritmetika v~tomto modelu (a¾ na triviální pøípady) nefunguje v~konstantním
  47 èase, datové struktury popsatelné pomocí pointerù (seznamy, stromy \dots) fungují
  48 pøímoèaøe, ov¹em pole musíme reprezentovat stromem, tak¾e indexování stojí
  49 $\Theta(\log n)$.
  50
  51 \s{Random Access Machine (RAM)} \cite{demaine} je rodinka modelù, které mají spoleèné to, ¾e
  52 pracují výhradnì s~(pøirozenými) èísly a ukládají je do~pamìti indexované
  53 opìt èísly. Instrukce v~programu (podobné assembleru) pracují s~operandy,
  54 které jsou buï konstanty nebo buòky pamìti adresované pøímo (èíslem buòky),
  55 pøípadnì nepøímo (index je ulo¾en v~nìjaké buòce adresované pøímo).
  56 Je~vidìt, ¾e tento model je alespoò tak silný jako PM, proto¾e odkazy
  57 pomocí pointerù lze v¾dy nahradit indexováním.
  58
  59 Pokud ov¹em povolíme poèítat s~libovolnì velkými èísly v~konstantním èase,
  60 dostaneme velice silný paralelní poèítaè, na~nìm¾ spoèítáme témìø v¹e
  61 v~konstantním èase (modulo kódování vstupu). Proto musíme model nìjak
  62 omezit, aby byl realistický, a~to lze udìlat více zpùsoby:
  63
  64 \itemize\ibull
  65 \:{\I Zavést logaritmickou cenu instrukcí} -- operace trvá tak dlouho,
  66 kolik je poèet bitù èísel, s~nimi¾ pracuje, a~to vèetnì adres v~pamìti.
  67 Elegantnì odstraní absurdity, ale je dost tì¾ké odhadovat èasové slo¾itosti;
  68 u~vìt¹iny normálních algoritmù nakonec po~dlouhém poèítání vyjde, ¾e mají
  69 slo¾itost $\Theta(\log n)$-krát vìt¹í ne¾ v~neomezeném RAMu.
  70
  71 \:{\I Omezit velikost èísel} na~nìjaký pevný poèet bitù (budeme mu øíkat
  72 {\I ¹íøka slova} a znaèit~$w$) a operace ponechat v~èase $\O(1)$.
  73 Abychom mohli alespoò adresovat vstup, musí být $w\ge\log N$,
  74 kde $N$ je celková velikost vstupu.
  75 Jeliko¾ aritmetiku s~$\O(1)$-násobnou pøesností lze simulovat s~konstantním
  76 zpomalením, mù¾eme pøedpokládat, ¾e $w=\Omega(\log N)$, tedy ¾e lze pøímo pracovat
  77 s~èísly polynomiálnì velkými vzhledem k~$N$. Je¹tì bychom si mìli ujasnit,
  78 jakou mno¾inu operací povolíme:
  79
  80 \itemize\ibull
  81 \:{\I Word-RAM} -- \uv{céèkové} operace: $+$, $-$, $*$, $/$, $\bmod$ (aritmetika);
  82 $\shl$, $\shr$ (bitové posuvy); $\land$, $\lor$, $\oplus$, $\opnot$ (bitový and, or, xor a negace).
  83
  84 \:{\I $AC^0$-RAM} -- libovolné funkce vyèíslitelné hradlovou sítí polynomiální
  85 velikosti a konstantní hloubky s~hradly o~libovolnì mnoha vstupech.\foot{Pro zvídavé:
  86 $AC^k$ je tøída v¹ech funkcí spoèítetelných polynomiálnì velkou hradlovou
  87 sítí hloubky $\O(\log^k n)$ s~libovolnì-vstupovými hradly a $NC^k$ toté¾
  88 s~omezením na~hradla se dvìma vstupy. V¹imnìte si, ¾e $NC^0\subseteq AC^0 \subseteq NC^1 \subseteq AC^1 \subseteq NC^2 \subseteq \ldots$.}
  89 To je teoreticky èist¹í, patøí sem v¹e z~pøedchozí skupiny mimo násobení,
  90 dìlení a modula, a~také spousta dal¹ích operací.
  91
  92 \:{\I Kombinace pøedchozího} -- tj. pouze operace Word-RAMu, které jsou v~$AC^0$.
  93 \endlist
  94
  95 \endlist
  96
  97 Ve~zbytku této kapitoly uká¾eme, ¾e na~RAMu lze poèítat mnohé vìci
  98 efektivnìji ne¾ na~PM. Zamìøíme se na~Word-RAM, ale podobné konstrukce
  99 jdou provést i na~$AC^0$-RAMu. (Kombinace obou omezení vede ke~slab¹ímu modelu.)
 100
 101 \h{Van Emde-Boas Trees}
 102
 103 Van Emde-Boas Trees neboli VEBT \cite{boas77} jsou RAMová struktura, která si pamatuje mno¾inu prvkù $X$ z~nìjakého
 104 omezeného universa $X \subseteq \{0,\ldots,U-1\}$, a umí s~ní provádìt
 105 \uv{stromové operace} (vkládání, mazání, nalezení následníka apod.) v~èase
 106 $\O(\log\log U)$. Pomocí takové struktury pak napøíklad doká¾eme:
 107 $$\vbox{\halign{
 108 #\hfil\quad     &#\hfil\quad            &#\hfil\cr
 109                 & pomocí VEBT           &nejlep¹í známé pro celá èísla \cr
 110 \noalign{\smallskip\hrule\smallskip}
 111 tøídìní         &$\O(n\log\log U)$      &$\O(n\log\log n)$ \cite{han:sort} \cr
 112 MST             &$\O(m\log\log U)$      &$\O(m)$ [viz pøí¹tí kapitola]\cr
 113 Dijkstra        &$\O(m\log\log U)$      &$\O(m+n\log\log n)$ \cite{thorup:pq}, neorientovanì $\O(m)$~\cite{thorup:usssp}\cr
 114 }}$$
 115 My se pøidr¾íme ekvivalentní, ale jednodu¹¹í definice podle Erika Demaine~\cite{demaine}.
 116
 117 \s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$)
 118 obsahuje:
 119
 120 \itemize\ibull
 121
 122 \:\<min>, \<max> reprezentované mno¾iny (mohou být i nedefinovaná, pokud je mno¾ina moc malá),
 123
 124 \:{\I pøihrádky} $P_0, \ldots, P_{\sqrt{U}}$ obsahující zbývající
 125 hodnoty.\foot{Alespoò jedno z~\<min>, \<max> musí být ulo¾eno zvlá¹»,
 126 aby strom obsahující pouze jednu hodnotu nemìl ¾ádné podstromy.
 127 My jsme pro eleganci struktury zvolili ulo¾it zvlá¹» obojí.}
 128 Hodnota $x$ padne do~$P_{\lfloor x/\sqrt{U} \rfloor}$.
 129 Ka¾dá pøihrádka je ulo¾ena jako VEBT($\sqrt{U}$), který obsahuje pøíslu¹ná
 130 èísla $\bmod\sqrt{U}$. [Bity ka¾dého èísla jsme tedy rozdìlili na~vy¹¹ích $k/2$,
 131 které indexují pøihrádku, a~ni¾¹ích $k/2$ uvnitø pøihrádky.]
 132
 133 \:Navíc je¹tì {\I \uv{sumární}} VEBT($\sqrt{U}$) obsahující èísla neprázdných pøihrádek.
 134 \endlist
 135
 136 \s{Operace} se~strukturou budeme provádìt následovnì. Budeme si pøitom pøedstavovat,
 137 ¾e v~pøihrádkách jsou ulo¾ena pøímo èísla reprezentované mno¾iny, nikoliv jen èásti
 138 jejich bitù -- z~èísla pøihrádky a hodnoty uvnitø pøihrádky ostatnì doká¾eme celou
 139 hodnotu rekonstruovat a naopak hodnotu kdykoliv rozlo¾it na~tyto èásti.
 140
 141 \>\<FindMin> -- minimum nalezneme v~koøeni v~èase $\O(1)$.
 142
 143 \>$\<Find>(x)$ -- pøímoèaøe rekurzí pøes pøihrádky v~èase $\O(k)$.
 144
 145 \>$\<Insert>(x)$:
 146 \algo
 147 \:O¹etøíme triviální stromy (prázdný a jednoprvkový)
 148 \:Je-li tøeba, prohodíme $x$ s \<min>, \<max>.
 149 \:Prvek $x$ padne do pøihrádky $P_i$, která je buï:
 150 \::prázdná $\Rightarrow$ \<Insert> hodnoty~$i$ do~sumárního stromu a zalo¾ení
 151 triviálního stromu pro pøihrádku; nebo
 152 \::neprázdná $\Rightarrow$ pøevedeme na~\<Insert> v~podstromu.
 153 \endalgo
 154
 155 V~ka¾dém pøípadì buï rovnou skonèíme nebo pøevedeme na~\<Insert> v~jednom stromu
 156 ni¾¹ího øádu a k~tomu vykonáme konstantní práci. Celkem tedy $\O(k)$.
 157
 158 \>$\<Delete>(x)$ -- smazání prvku bude opìt pracovat v~èase $\O(k)$.
 159 \algo
 160 \:O¹etøíme triviální stromy (jednoprvkový a dvouprvkový).
 161 \:Pokud ma¾eme \<min> (analogicky \<max>), nahradíme ho minimem
 162 z~první neprázdné pøihrádky (tu najdeme podle sumárního stromu v~konstantním èase)
 163 a pøevedeme na~\<Delete> v~této pøihrádce.
 164 \:Prvek~$x$ padne do~pøihrádky $P_i$, která je buï:
 165 \::jednoprvková $\Rightarrow$ zru¹ení pøihrádky a \<Delete> ze~sumárního stromu; nebo
 166 \::vìt¹í $\Rightarrow$ \<Delete> ve~stromu pøihrádky.
 167 \endalgo
 168
 169 \>$\<Succ>(x)$ -- nejmen¹í prvek vìt¹í ne¾~$x$, opìt v~èase $\O(k)$:
 170
 171 \algo
 172 \:Triviální pøípady: pokud $x<\<min>$, vrátíme \<min>; pokud $x\ge\<max>$,
 173 vrátíme, ¾e následník neexistuje.
 174 \:Prvek~$x$ padne do~pøihrádky $P_i$ a buïto:
 175 \::$P_i$ je prázdná nebo $x=\<max>(P_i)$ $\Rightarrow$ pomocí \<Succ>
 176 v~sumárním stromu najdeme nejbli¾¹í dal¹í neprázdnou pøihrádku $P_j$:
 177 \:::existuje-li $\Rightarrow$ vrátíme $\<min>(P_j)$,
 178 \:::neexistuje-li $\Rightarrow$ vrátíme \<max>.
 179 \::nebo $x<\<max>(P_i)$ $\Rightarrow$ pøevedeme na~\<Succ> v~$P_i$.
 180 \endalgo
 181
 182 Slo¾itosti operací jsou pìkné, ale nesmíme zapomenout, ¾e strukturu
 183 je na~poèátku nutné inicializovat, co¾ trvá $\Omega(\sqrt U)$.\foot{Svádí
 184 to k~nápadu ponechat pøihrádky neinicializované a nejdøíve se v¾dy zeptat
 185 sumárního stromu, ale tím bychom si pokazili èasovou slo¾itost.}
 186 Z~následujících úvah ov¹em vyplyne, ¾e si inicializaci mù¾eme
 187 odpustit.
 188
 189 \h{Modely inicializace}
 190
 191 \>Jak mù¾e být definován obsah pamìti na~poèátku výpoètu:
 192
 193 \s{\uv{Pøi odchodu zhasni}:} Zavedeme, ¾e pamì» RAMu je na~poèátku
 194 inicializována nulami a program ji po~sobì musí uklidit (to je nutné,
 195 aby programy ¹lo iterovat). To u~VEBT není problém zaøídit.
 196
 197 \s{Neinicializovano:} Na~¾ádné konkrétní hodnoty se nemù¾eme spolehnout,
 198 ale je definováno, ¾e neinicializovanou buòku mù¾eme pøeèíst a dostaneme
 199 nìjakou korektní, i kdy¾ libovolnou, hodnotu. Tehdy nám pomù¾e:
 200
 201 {\narrower
 202
 203 \s{Vìta:} Buï $P$ program pro Word-RAM s~nulami inicializovanou
 204 pamìtí, bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM
 205 s~neinicializovanou pamìtí poèítající toté¾ v~èase~$\O(T(n))$.
 206
 207 \proof Bìhem výpoètu si budeme pamatovat, do~kterých pamì»ových
 208 bunìk u¾ bylo nìco zapsáno, a~které tedy mají definovanou hodnotu.
 209 Prokládanì ulo¾íme do pamìti dvì pole:
 210 $M$, co¾ bude pamì» pùvodního stroje, a~$L$ -- seznam èísel bunìk
 211 v~$M$, do~kterých u¾ program zapsal. Pøitom $L[0]$ bude udávat
 212 délku seznamu~$L$.
 213
 214 Program nyní zaène tím, ¾e vynuluje $L[0]$ a bude simulovat pùvodní
 215 program, pøièem¾ kdykoliv ten bude chtít pøeèíst nìjakou buòku
 216 z~$M$, podíváme se do~$L$, zda u¾ je inicializovaná, a~pøípadnì
 217 vrátíme nulu a buòku pøipí¹eme do~$L$.
 218
 219 To je funkèní, ale pomalé. Redukci tedy vylep¹íme tak, ¾e zalo¾íme dal¹í
 220 prolo¾ené pole~$R$, jeho¾ hodnota $R[i]$ bude øíkat, kde v~$L$ se vyskytuje
 221 èíslo $i$-té buòky, nebo bude neinicializována, pokud
 222 takové místo dosud neexistuje.
 223
 224 Pøed ètením $M[i]$ se teï podíváme na~$R[i]$ a ovìøíme, zda $R[i]$ nele¾í
 225 mimo seznam~$L$ a zda je $L[R[i]]=i$. Tím v~konstantním èase zjistíme,
 226 jestli je $M[i]$ ji¾ inicializovaná, a~jsme také schopni tuto informaci
 227 v~tém¾e èase udr¾ovat.
 228 \qed
 229
 230 }
 231
 232 \s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst.
 233 V~tomto pøípadì nejsme schopni deterministické redukce, ale alespoò
 234 mu¾eme pou¾ít randomizovanou -- ukládat si obsah pamìti do~hashovací
 235 tabulky, co¾ pøí pou¾ití universálního hashování dá~slo¾itost $\O(1)$
 236 na~operaci v~prùmìrném pøípadì.
 237
 238 \h{Technické triky}
 239
 240 VEBT nedosahují zdaleka nejlep¹ích mo¾ných parametrù -- lze sestrojit
 241 i struktury pracující v~konstantním èase. To v~následující kapitole také
 242 udìláme, ale nejdøíve v~této ponìkud technické stati vybudujeme repertoár
 243 základních operací proveditelných na~Word-RAMu v~konstantním èase.
 244
 245 \>Rozcvièka: {\I nejpravìj¹í jednièka} ve~dvojkovém èísle (hodnota, nikoliv pozice):
 246 \alik{
 247         x&=\0\1\9\9\9\0\1\1\0\0\0\0\0\0 \cr
 248  x - 1&=\0\1\9\9\9\0\1\0\1\1\1\1\1\1 \cr
 249  x \land (x - 1)&=\0\1\9\9\9\0\1\0\0\0\0\0\0\0 \cr
 250  x \oplus (x \land (x - 1))&=\0\0\9\9\9\0\0\1\0\0\0\0\0\0 \cr}
 251
 252 \>Nyní uká¾eme, jak RAM pou¾ívat jako vektorový poèítaè, který umí paralelnì
 253 poèítat se v¹emi prvky vektoru, pokud se dají zakódovat do~jediného slova.
 254 Libovolný $n$-slo¾kový vektor, jeho¾ slo¾ky jsou $b$-bitová èísla
 255 ($n(b+1)\le w$), zakódujeme poskládáním jednotlivých slo¾ek vektoru za~sebe,
 256 prolo¾enì nulovými bity:
 257 \alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr}
 258
 259 \>S~vektory budeme provádìt následující operace: (latinkou znaèíme vektory,
 260 alfabetou èísla, \0 a \1 jsou jednotlivé bity, $(\ldots)^k$ je $k$-násobné
 261 opakování binárního zápisu)
 262
 263 \itemize\ibull
 264
 265 \:$\<Replicate>(\alpha)$ -- vytvoøí vektor $(\alpha,\alpha,\ldots,\alpha)$:
 266  \alik{\alpha*(\0^b\1)^n \cr}
 267
 268 \:$\<Sum>(x)$ -- seète v¹echny slo¾ky vektoru (pøedpokládáme, ¾e se souèet vejde do~$b$~bitù):
 269
 270 \numlist\nalpha
 271 \:vymodulením èíslem $\1^{b+1}$ (proto¾e $\1\0^{b+1}\bmod \1^{b+1}=1$), èi
 272 \:násobením vhodnou konstantou:
 273 \setbox0=\hbox{~$x_{n-1}$}
 274 \slotwd=\wd0
 275 \def\.{\[]}
 276 \def\z{\[\0^b\1]}
 277 \def\dd{\slot{$\cdots$}}
 278 \def\vd{\slot{$\vdots$}}
 279 \def\rule{\noalign{\medskip\nointerlineskip}
 280 $\hrulefill$\cr
 281 \noalign{\nointerlineskip\medskip}}
 282
 283 \alik{
 284 \[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
 285 *~~ \z \dd \z\z\z \cr
 286 \rule
 287 \[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
 288 \[x_{n-1}] \[x_{n-2}] \dd \[x_1] \[x_0] \. \cr
 289 \[x_{n-1}] \[x_{n-2}] \[x_{n-3}] \dd \[x_0] \. \. \cr
 290 \vd\vd\vd\vd\.\.\.\cr
 291 \[x_{n-1}] \dd \[x_2]\[x_1]\[x_0] \. \. \. \. \cr
 292 \rule
 293 \[r_{n-1}] \dd \[r_2] \[r_1] \[s_n] \dd \[s_3] \[s_2] \[s_1] \cr
 294 }
 295 Zde je výsledkem dokonce vektor v¹ech èásteèných souètù:
 296 $s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{n-1}x_i$.
 297 \endlist
 298
 299 \:$\<Cmp>(x,y)$ -- paralelní porovnání dvou vektorù: $i$-tá slo¾ka výsledku je~1, pokud
 300 $x_i<y_i$, jinak~0.
 301
 302 \setbox0=\vbox{\hbox{~$x_{n-1}$}\hbox{~$y_{n-1}$}}
 303 \slotwd=\wd0
 304 \alik{
 305    \1 \[x_{n-1}] \1 \[x_{n-2}] \[\cdots] \1 \[x_1] \1 \[x_0]  \cr
 306 -~ \0 \[y_{n-1}] \0 \[y_{n-2}] \[\cdots] \0 \[y_1] \0 \[y_0]  \cr
 307 }
 308
 309 Ve~vektoru $x$ nahradíme prokládací nuly jednièkami a odeèteme vektor~$y$.
 310 Ve~výsledku se tyto jednièky zmìní na~nuly právì u tìch slo¾ek, kde $x_i < y_i$.
 311 Pak je ji¾ staèí posunout na~správné místo a okolní bity vynulovat a znegovat.
 312
 313 \:$\<Rank>(\alpha,x)$ -- spoèítá, kolik slo¾ek vektoru~$x$ je men¹ích ne¾~$\alpha$:
 314 $$\<Rank>(\alpha,x) = \<Sum>(\<Cmp>(\<Replicate>(\alpha),x)).$$
 315
 316 \:$\<Insert>(\alpha,x)$ -- zatøídí hodnotu $\alpha$ do~setøídìného vektoru~$x$:
 317
 318 Zde staèí pomocí operace \<Rank> zjistit, na~jaké místo novou hodnotu
 319 zatøídit, a~pak to pomocí bitových operací provést (\uv{roz¹oupnout}
 320 existující hodnoty).
 321
 322 \:$\<Unpack>(\alpha)$ -- vytvoøí vektor, jeho¾ slo¾ky jsou bity zadaného èísla
 323 (jinými slovy prolo¾í bity bloky $b$~nul).
 324
 325 Nejdøíve èíslo~$\alpha$ replikujeme, pak andujeme vhodnou bitovou maskou,
 326 aby v~$i$-té slo¾ce zùstal pouze $i$-tý bit a ostatní se vynulovaly,
 327 a pak provedeme $\<Cmp>$ s~vektorem reprezentovaným touté¾ bitovou maskou.
 328
 329 \:$\<Unpack>_\varphi(\alpha)$ -- podobnì jako pøedchozí operace, ale bity je¹tì
 330 prohází podle nìjaké pevné funkce $\varphi$:
 331
 332 Staèí zvolit bitovou masku, která v~$i$-té slo¾ce ponechá právì $\varphi(i)$-tý bit.
 333
 334 \:$\<Pack>(x)$ -- dostane vektor nul a jednièek a vytvoøí èíslo, jeho¾ bity
 335 jsou právì slo¾ky vektoru (jinými slovy ¹krtne nuly mezi bity):
 336
 337 Pøedstavíme si, ¾e slo¾ky èísla jsou o~jeden bit krat¹í a provedeme \<Sum>.
 338 Napøíklad pro $n=4$ a $b=4$:
 339
 340 \setbox0=\hbox{$x_3$}
 341 \slotwd=\wd0
 342 \def\z{\[\0]}
 343
 344 \def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
 345 \def\.{\hphantom{\|}}
 346
 347 \alik{
 348 \|\z\.\z\.\z\.\z\.\[x_3]\|\z\.\z\.\z\.\z\.\[x_2]\|\z\.\z\.\z\.\z\[x_1]\|\z\.\z\.\z\.\z\.\[x_0]\|\cr
 349 \|\z\.\z\.\z\.\z\|\[x_3]\.\z\.\z\.\z\|\z\.\[x_2]\.\z\.\z\|\z\.\z\[x_1]\.\z\|\z\.\z\.\z\.\[x_0]\|\cr
 350 }
 351
 352 Jen si musíme dát pozor na~to, ¾e vytvoøený vektor s~krat¹ími slo¾kami
 353 není korektnì prostrkán nulami. Konstrukce \<Sum> pomocí modula proto
 354 nebude správnì fungovat a místo $\1^b$ vygeneruje $\0^b$. To mù¾eme
 355 buï o¹etøit zvlá¹», nebo pou¾ít konstrukci pøes násobení, které
 356 to nevadí.
 357
 358 \endlist
 359
 360 \>Nyní je¹tì nìkolik operací s~normálními èísly. Chvíli pøedpokládejme,
 361 ¾e pro~$b$-bitová èísla na~vstupu budeme mít k~dispozici $b^2$-bitový
 362 pracovní prostor, tak¾e budeme moci pou¾ívat vektory s~$b$ slo¾kami
 363 po~$b$ bitech.
 364
 365 \itemize\ibull
 366
 367 \:$\#1(\alpha)$ -- spoèítá jednièkové bity v~zadaném èísle.
 368
 369 Staèí provést \<Unpack> a následnì \<Sum>.
 370
 371 \:$\<Permute>_\pi(\alpha)$ -- pøehází bity podle zadané fixní permutace.
 372
 373 Provedeme $\<Unpack>_\pi$ a \<Pack> zpìt.
 374
 375 \:$\<LSB>(\alpha)$ -- Least Significant Bit (pozice nejni¾¹í jednièky):
 376
 377 Podobnì jako v~rozcvièce nejdøíve vytvoøíme èíslo, které obsahuje
 378 nejni¾¹í jednièku a vpravo od~ní dal¹í jednièky, a~pak tyto jednièky
 379 posèítáme pomocí $\#1$:
 380
 381 \alik{
 382 \alpha&=                        \9\9\9\9\9\1\0\0\0\0\cr
 383 \alpha-1&=                      \9\9\9\9\9\0\1\1\1\1\cr
 384 \alpha\oplus(\alpha-1)&=        \0\9\9\9\0\1\1\1\1\1\cr
 385 }
 386
 387 \:$\<MSB>(\alpha)$ -- Most Significant Bit (pozice nejvy¹¹í jednièky):
 388
 389 Z~\<LSB> pomocí zrcadlení (operací \<Permute>).
 390
 391 \endlist
 392
 393 \>Poslední dvì operace doká¾eme spoèítat i v~lineárním prostoru, napøíklad
 394 pro \<MSB> takto: Rozdìlíme èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$.
 395 Pak pro ka¾dý blok zjistíme, zda v nìm je aspoò jedna jednièka, zavoláním
 396 $\<Cmp>(0,x)$. Pomocí \<Pack> z~toho dostaneme slovo~$y$ odmocninové
 397 délky, jeho¾ bity indikují neprázdné bloky. Na~toto èíslo zavoláme pøedchozí
 398 kvadratické \<MSB> a zjistíme index nejvy¹¹ího neprázdného bloku.
 399 Ten pak izolujeme a druhým voláním kvadratického algoritmu najdeme nejlevìj¹í
 400 jednièku uvnitø nìj.\foot{Dopou¹tíme se drobného podvùdku -- vektorové operace
 401 pøedpokládaly prostrkané nuly a ty tu nemáme. Mù¾eme si je ale snadno poøídit
 402 a bity, které jsme nulami pøepsali, prostì zpracovat zvlá¹».}
 403
 404 \references
 405 \bye