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.3\hsize\hfil $ ##$&\hbox to 0.4\hsize{${}##$ \hss}\cr
  22 #1}
  23 \medskip
  24 }
  25
  26 \prednaska{7}{Výpoèetní modely}{zapsal Zdenìk Vilu¹ínský }
  27
  28 \h{Druhy výpoèetních modelù}
  29
  30 Kdy¾ jsme v~pøede¹lých kapitolách studovali algoritmy, nezabývali jsme se tím,
  31 v~jakém pøesnì výpoèetním modelu pracujeme. Konstrukce, které jsme pou¾ívali,
  32 toti¾ fungovaly ve~v¹ech obvyklých modelech a mìly tam stejnou èasovou
  33 i prostorovu slo¾itost. Ne~v¾dy tomu tak je, tak¾e se výpoèetním modelùm
  34 podívejme na~zoubek trochu blí¾e.
  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 $\O(\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 $\O(\log n)$-krát vìt¹í ne¾ v~neomezeném RAMu.
  70
  71 \:{\I Omezit velikost èísel} na~$w$ bitù a operace ponechat v~èase $\O(1)$.
  72 Jeliko¾ potøebujeme umìt alespoò adresovat vstup, je $w=\Omega(\log n)$.%
  73 \foot{Pøesnìji, plyne z~toho jen, ¾e $w\ge\log_2 n$, ale to je ekvivalentní,
  74 proto¾e aritmetiku s~$\O(1)$-násobnou pøesností mù¾eme simulovat
  75 s~konstantním zpomalením.  S~$\O(\log n)$ bity se ov¹em pracuje daleko
  76 pøíjemnìji, proto¾e si mù¾eme v¾dy dovolit ukládat èísla polynomiálnì
  77 velká vzhledem k~$n$.} Je¹tì bychom si mìli ujasnit, jakou mno¾inu
  78 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 spoèítatelné hradlovou sítí polynomiální
  85 velikosti a konstantní hloubky s~hradly o~libovolné mnoho 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 V~zbytku této kapitoly uká¾eme, ¾e na~RAMu lze poèítat mnohé vìci
  98 efektivnìji ne¾ na~PM. Zamìøíme se pøevá¾nì na~Word-RAM, 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 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
 108 $$\vbox{\halign{
 109 #\hfil\quad     &#\hfil\quad            &#\hfil\cr
 110                 & pomocí VEBT           &nejlep¹í známé pro celá èísla \cr
 111 \noalign{\smallskip\hrule\smallskip}
 112 tøídìní         &$\O(n\log\log U)$      &$\O(n\log\log n)$ \cr
 113 MST             &$\O(m\log\log U)$      &$\O(m)$ \cr
 114 Dijkstra        &$\O(m\log\log U)$      &$\O(m+n\log\log n)$, neorientovanì $\O(m)$\cr
 115 }}$$
 116
 117 \s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$)
 118 obsahuje: (ekvivalentní formulace podle \cite{demaine})
 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 zvlá¹» obojí.}
 128 Hodnota $x$ padne do~$P_{\lfloor x/\sqrt{U} \rfloor}$.
 129 Ka¾dá pøíhrádka je ulo¾ena jako VEBT($\sqrt{U}$), který obsahuje pøíslu¹ná èísla $\bmod \sqrt{U}$.
 130 [Bity ka¾dého èísla jsme tedy rozdìlili na~vy¹¹ích $k/2$, které indexují
 131 pøíhrádku, a~ni¾¹ích $k/2$ uvnitø pøíhrá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ì:
 137
 138 \>\<FindMin> -- minimum nalezneme v~koøeni v~èase $\O(1)$.
 139
 140 \>$\<Find>(x)$ -- pøímoèaøe rekurzí pøes pøíhrádky v~èase $\O(k)$.
 141
 142 \>$\<Insert>(x)$:
 143 \algo
 144 \:O¹etøíme triviální stromy (prázdný a jednoprvkový)
 145 \:Je-li tøeba, prohodíme $x$ s \<min>, \<max>
 146 \:Prvek $x$ padne do pøihrádky $P_i$, která je buï:
 147 \::prázdná $\Rightarrow$ Insert~$i$ do~sumárního stromu a zalo¾ení
 148 triviálního stromu pro pøihrádku; nebo
 149 \::neprázdná $\Rightarrow$ pøevedu na~Insert v~podstromu.
 150 \endalgo
 151
 152 V~ka¾dém pøípadì buï rovnou skonèíme nebo pøevedeme na~Insert v~jednom stromu
 153 ni¾¹ího øádu a k~tomu vykonáme konstantní práci. Celkem tedy $\O(k)$.
 154
 155 \>$\<Delete>(x)$: (slo¾itost opìt $\O(k)$)
 156 \algo
 157 \:O¹etøíme triviální stromy (jednoprvkový a dvouprvkový)
 158 \:Pokud ma¾eme \<min> (analogicky \<max>), nahradíme ho minimem
 159 z~první neprázdné pøíhrádky (tu najdeme podle sumárního stromu)
 160 a pøevedeme na~Delete v~této pøíhrádce.
 161 \:Prvek~$x$ padne do~pøíhrádky $P_i$, která je buï:
 162 \::jednoprvková $\Rightarrow$ zru¹ení pøíhrádky a Delete ze~sumárního stromu; nebo
 163 \::vìt¹í $\Rightarrow$ Delete ve~stromu pøíhrádky.
 164 \endalgo
 165
 166 \>$\<Succ>(x)$: (nalezne nejmen¹í prvek vìt¹í ne¾~$x$, opìt v~èase $\O(k)$)
 167
 168 \algo
 169 \:Triviální pøípady: pokud $x<\<min>$, vrátíme \<min>; pokud $x\ge\<max>$,
 170 vrátíme, ¾e následník neexistuje.
 171 \:Prvek~$x$ padne do~pøíhrádky $P_i$ a buïto:
 172 \::$P_i$ je prázdná nebo $x=\<max>(P_i)$ $\Rightarrow$ pomocí Succ
 173 v~sumárním stromu najdeme nejbli¾¹í dal¹í neprázdnou pøíhrádku $P_j$:
 174 \:::existuje-li $\Rightarrow$ vrátíme $\<min>(P_j)$,
 175 \:::neexistuje-li $\Rightarrow$ vrátíme \<max>.
 176 \::nebo $x<\<max>(P_i)$ $\Rightarrow$ pøevedeme na~Succ v~$P_i$.
 177 \endalgo
 178
 179 Slo¾itosti operací jsou pìkné, ale nesmíme zapomenout, ¾e strukturu
 180 je na~poèátku nutné inicializovat, co¾ trvá $\Omega(\sqrt U)$.
 181 Z~následujících úvah ov¹em vyplyne, ¾e si inicializaci mù¾eme
 182 odpustit.
 183
 184 \h{Modely inicializace}
 185
 186 \>Jak mù¾e definován obsah pamìti na~poèátku výpoètu:
 187
 188 \s{\uv{Pøi odchodu zhasni}:} Zavedeme, ¾e pamì» RAMu je na~poèátku
 189 inicializována nulami a program ji po~sobì musí uklidit (to je nutné,
 190 aby programy ¹lo iterovat). To u~VEBT není problém zaøídit.
 191
 192 \s{Neinicializovano:} Na~¾ádné konkrétní hodnoty se nemù¾eme spolehnout,
 193 ale je definováno, ¾e neinicializovanou buòku mù¾eme pøeèíst a dostaneme
 194 nìjakou korektní, i kdy¾ libovolnou, hodnotu. Tehdy nám pomù¾e:
 195
 196 {\narrower
 197
 198 \s{Vìta:} Buï $P$ program pro Word-RAM s~nulami inicializovanou
 199 pamìtí bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM
 200 s~neinicializovanou pamìtí poèítající toté¾ v~èase~$\O(T(n))$.
 201
 202 \s{Dùkaz:} Bìhem výpoètu si budeme pamatovat, ve~kterých pamì»ových
 203 buòkách u¾ nìco máme. Prokládanì ulo¾íme do pamìti dvì pole:
 204 $M$, co¾ bude pamì» pùvodního stroje, a~$L$ -- seznam èísel bunìk
 205 v~$M$, do~kterých u¾ program zapsal. Pøitom $L[0]$ bude udávat
 206 délku seznamu~$L$.
 207
 208 Program nyní zaène tím, ¾e vynuluje $L[0]$ a bude simulovat pùvodní
 209 program, pøièem¾ kdykoliv ten bude chtít pøeèíst nìjakou buòku
 210 z~$M$, podíváme se do~$L$, zda u¾ je inicializovaná, a~pøípadnì
 211 vrátíme nulu a buòku pøipí¹eme do~$L$.
 212
 213 To je funkèní, ale pomalé. Redukci tedy vylep¹íme tak, ¾e zalo¾íme dal¹í
 214 prolo¾ené pole~$R$, jeho¾ hodnota $R[i]$ bude øíkat, kde v~$L$ se vyskytuje
 215 èíslo $i$-té buòky, nebo bude neinicializována, pokud
 216 takové místo neexistuje.
 217
 218 Pøed ètením $M[i]$ se tedy podíváme na~$R[i]$ a ovìøíme, zda $R[i]$ nele¾í
 219 mimo seznam~$L$ a zda je $L[R[i]]=i$. Tím v~konstantním èase ovìøíme,
 220 jestli je $M[i]$ ji¾ inicializovaná, a~jsme také schopni tuto informaci
 221 v~tém¾e èase udr¾ovat.
 222 \qed
 223
 224 \todo{References}
 225 }
 226
 227 \s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst.
 228 V~tomto pøípadì nejsme schopni deterministické redukce, ale alespoò
 229 mu¾eme pou¾ít randomizovanou -- ukládat si obsah pamìti do~hashovací
 230 tabulky, co¾ pøí pou¾ití universálního hashování dá~slo¾itost $\O(1)$
 231 na~operaci v~prùmìrném pøípadì.
 232
 233 \h{Technické triky}
 234
 235 VEBT nedosahují zdaleka nejlep¹ích mo¾ných parametrù -- lze sestrojit
 236 i struktury pracující v~konstantním èase. To v~následující kapitole také
 237 udìláme, ale nejdøíve v~této ponìkud technické stati vybudujeme repertoár
 238 základních operací proveditelných na~Word-RAMu v~konstantním èase.
 239
 240 \>Rozcvièka: {\I nejpravìj¹í jednièka} ve~dvojkovém èísle (hodnota, nikoliv pozice):
 241 \alik{
 242         x&=\0\1\9\9\9\0\1\1\0\0\0\0\0\0 \cr
 243  x - 1&=\0\1\9\9\9\0\1\0\1\1\0\0\0\1 \cr
 244  x \land (x - 1)&=\0\1\9\9\9\0\1\0\0\0\0\0\0\0 \cr
 245  x \oplus (x \land (x - 1))&=\0\0\9\9\9\0\0\1\0\0\0\0\0\0 \cr}
 246
 247 \>Nyní uká¾eme, jak RAM pou¾ívat jako vektorový poèítaè, který umí paralelnì
 248 poèítat se v¹emi prvky vektoru, pokud se dají zakódovat do~jediného slova.
 249 Libovolný $n$-slo¾kový vektor, jeho¾ slo¾ky jsou $b$-bitová èísla
 250 ($n(b+1)\le w$), zakódujeme poskládáním jednotlivých slo¾ek vektoru za~sebe,
 251 prolo¾enì nulovými bity:
 252 \alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr}
 253
 254 \>S~vektory budeme provádìt následující operace:
 255
 256 \itemize\ibull
 257
 258 \:$\<Replicate>(\alpha)$ -- vytvoøí vektor $(\alpha,\alpha,\ldots,\alpha)$:
 259  \alik{\alpha*(\0^b\1)^n \cr}
 260
 261 \:$\<Sum>(x)$ -- seète v¹echny slo¾ky vektoru (pøedpokládáme, ¾e se vejdou do~$b$~bitù):
 262
 263 \numlist\nalpha
 264 \:vymodulením èíslem $\1^{b+1}$ (to funguje, proto¾e $\1\0^{b+1}\bmod \1^{b+1}=1$), nebo
 265 \:násobením vhodnou konstantou:
 266 \setbox0=\hbox{~$x_{n-1}$}
 267 \slotwd=\wd0
 268 \def\.{\[]}
 269 \def\z{\[\0^b\1]}
 270 \def\dd{\slot{$\cdots$}}
 271 \def\vd{\slot{$\vdots$}}
 272 \def\rule{\noalign{\medskip\nointerlineskip}
 273 $\hrulefill$\cr
 274 \noalign{\nointerlineskip\medskip}}
 275
 276 \alik{
 277 \[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
 278 *~~ \z \dd \z\z\z \cr
 279 \rule
 280 \[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
 281 \[x_{n-1}] \[x_{n-2}] \dd \[x_1] \[x_0] \. \cr
 282 \[x_{n-1}] \[x_{n-2}] \[x_{n-3}] \dd \[x_0] \. \. \cr
 283 \vd\vd\vd\vd\.\.\.\cr
 284 \[x_{n-1}] \dd \[x_2]\[x_1]\[x_0] \. \. \. \. \cr
 285 \rule
 286 \[r_{n-1}] \dd \[r_2] \[r_1] \[s_n] \dd \[s_3] \[s_2] \[s_1] \cr
 287 }
 288 Zde je výsledkem dokonce vektor v¹ech èásteèných souètù:
 289 $s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{n-1}x_i$.
 290 \endlist
 291
 292 \:$\<Cmp>(x,y)$ -- paralelní porovnání dvou vektorù: $i$-tá slo¾ka výsledku je~1, pokud
 293 $x_i<y_i$, jinak~0.
 294
 295 \setbox0=\vbox{\hbox{~$x_{n-1}$}\hbox{~$y_{n-1}$}}
 296 \slotwd=\wd0
 297 \alik{
 298    \1 \[x_{n-1}] \1 \[x_{n-2}] \[\cdots] \1 \[x_1] \1 \[x_0]  \cr
 299 -~ \0 \[y_{n-1}] \0 \[y_{n-2}] \[\cdots] \0 \[y_1] \0 \[y_0]  \cr
 300 }
 301
 302 Ve~vektoru $x$ nahradíme prokládací nuly jednièkami a odeèteme vektor~$y$.
 303 Ve~výsledku se tyto jednièky zmìní na~nuly právì u tìch slo¾ek, kde $x_i < y_i$.
 304 Pak je ji¾ staèí posunout na~správné místo a okolní bity vynulovat.
 305
 306 \:$\<Rank>(\alpha,x)$ -- spoèítá, kolik slo¾ek vektoru~$x$ je men¹ích ne¾~$\alpha$:
 307 $$\<Rank>(\alpha,x) = \<Sum>(\<Cmp>(\<Replicate>(\alpha),x)).$$
 308
 309 \:$\<Insert>(\alpha,x)$ -- zatøídí hodnotu $\alpha$ do~setøídìného vektoru~$x$:
 310
 311 Zde staèí pomocí operace \<Rank> zjistit, na~jaké místo novou hodnotu
 312 zatøídit, a~pak to pomocí bitových operací provést (\uv{roz¹oupnout}
 313 existující hodnoty).
 314
 315 \:$\<Unpack>(\alpha)$ -- vytvoøí vektor, jeho¾ slo¾ky jsou bity zadaného èísla
 316 (jinými slovy prolo¾í bity bloky $b$~nul).
 317
 318 Nejdøíve èíslo~$\alpha$ replikujeme, pak andujeme vhodnou bitovou maskou,
 319 aby v~$i$-té slo¾ce zùstal pouze $i$-tý bit a ostatní se vynulovaly,
 320 a pak provedeme $\<Cmp>$ s~vektorem reprezentovaným touté¾ bitovou maskou.
 321
 322 \:$\<Unpack>_\varphi(\alpha)$ -- podobnì jako pøedchozí operace, ale bity je¹tì
 323 prohází podle nìjaké pevné funkce $\varphi$:
 324
 325 Staèí zvolit bitovou masku, která na~$i$-té pozici ponechá právì $\varphi(i)$-tý bit.
 326
 327 \:$\<Pack>(x)$ -- dostane vektor nul a jednièek a vytvoøí èíslo, jeho¾ bity
 328 jsou právì slo¾ky vektoru (jinými slovy ¹krtne nuly mezi bity):
 329
 330 Pøedstavíme si, ¾e slo¾ky èísla jsou o~jeden bit krat¹í a provedeme \<Sum>.
 331 Napøíklad pro $n=4$ a $b=4$:
 332
 333 \setbox0=\hbox{$x_3$}
 334 \slotwd=\wd0
 335 \def\z{\[\0]}
 336
 337 \def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
 338 \def\.{\hphantom{\|}}
 339
 340 \alik{
 341 \|\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
 342 \|\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
 343 }
 344
 345 Jen si musíme dát pozor na~to, ¾e vytvoøený vektor s~krat¹ími slo¾kami
 346 není korektnì prostrkán nulami. Konstrukce \<Sum> pomocí modula proto
 347 nebude správnì fungovat a místo $\1^b$ vygeneruje $\0^b$, co¾ mù¾eme
 348 buïto o¹etøit zvlá¹», nebo pou¾ít konstrukci pøes násobení, které
 349 to nevadí.
 350
 351 \endlist
 352
 353 \>Nyní je¹tì nìkolik operací s~normálními èísly. Zatím pøedpokládejme,
 354 ¾e pro~$b$-bitová èísla na~vstupu budeme mít k~dispozici $b^2$-bitový
 355 pracovní prostor, tak¾e budeme moci pou¾ívat vektory s~$b$ slo¾kami
 356 po~$b$ bitech.
 357
 358 \itemize\ibull
 359
 360 \:$\#1(\alpha)$ -- spoèítá jednièkové bity v~zadaném èísle.
 361
 362 Staèí provést \<Unpack> (výsledek se dokonce vejde do~$b\log b$ bitù)
 363 a následnì \<Sum>.
 364
 365 \:$\<Permute>_\pi(\alpha)$ -- pøehází bity podle zadané fixní permutace.
 366
 367 Provedeme $\<Unpack>_\pi$ a \<Pack> zpìt.
 368
 369 \:$\<LSB>(\alpha)$ -- Least Significant Bit (pozice nejni¾¹í jednièky):
 370
 371 Podobnì jako v~rozcvièce nejdøíve vytvoøíme èíslo, které obsahuje
 372 nejni¾¹í jednièku a vpravo od~ní dal¹í jednièky, a~pak tyto jednièky
 373 posèítáme pomocí $\#1$:
 374
 375 \alik{
 376 \alpha&=                        \9\9\9\9\9\1\0\0\0\0\cr
 377 \alpha-1&=                      \9\9\9\9\9\0\1\1\1\1\cr
 378 \alpha\oplus(\alpha-1)&=        \0\9\9\9\0\1\1\1\1\1\cr
 379 }
 380
 381 \:$\<MSB>(\alpha)$ -- Most Significant Bit (pozice nejvy¹¹í jednièky):
 382
 383 Z~\<LSB> pomocí zrcadlení (operací \<Permute>).
 384
 385 \endlist
 386
 387 \>Poslední dvì operace doká¾eme spoèítat i v~lineárním prostoru, napøíklad
 388 pro \<MSB> takto: Rozdìlíme èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$.
 389 Pak pro ka¾dý blok zjistíme, zda v nìm je aspoò jedna jednièka, zavoláním
 390 $\<Cmp>(0,x)$. Pomocí \<Pack> z~toho dostaneme slovo~$y$ odmocninové
 391 délky, jeho¾ bity indikují neprázdné bloky. Na~toto èíslo zavoláme pøedchozí
 392 kvadratické \<MSB>, èím¾ zjistíme index nejvy¹¹ího neprázdného bloku.
 393 Ten pak izolujeme a druhým voláním kvadratického algoritmu najdeme nejlevìj¹í
 394 jednièku uvnitø nìj.\foot{Dopou¹tíme se drobného podvùdku -- vektorové operace
 395 pøedpokládaly prostrkané nuly a ty tu nemáme. Mù¾eme si je ale snadno poøídit
 396 a bity, které jsme nulami pøepsali, prostì zpracovat zvlá¹».}
 397
 398 \references
 399 \bye