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^k=2^{2^\ell}$)
 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\medskip
 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 %\medskip}
 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
 258 \nobreak
 259 \alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr}
 260
 261 \>S~vektory budeme provádět následující operace: (latinkou značíme vektory,
 262 alfabetou čísla, \0 a \1 jsou jednotlivé bity, $(\ldots)^k$ je $k$-násobné
 263 opakování binárního zápisu)
 264
 265 \itemize\ibull
 266
 267 \:$\<Replicate>(\alpha)$ -- vytvoří vektor $(\alpha,\alpha,\ldots,\alpha)$:
 268  \alik{\alpha*(\0^b\1)^n \cr}
 269
 270 \:$\<Sum>(x)$ -- sečte všechny složky vektoru (předpokládáme, že se součet vejde do~$b$~bitů):
 271
 272 \numlist\nalpha
 273 \:vymodulením číslem $\1^{b+1}$ (protože $\1\0^{b+1}\bmod \1^{b+1}=1$), či
 274 \:násobením vhodnou konstantou:
 275 \setbox0=\hbox{~$x_{n-1}$}
 276 \slotwd=\wd0
 277 \def\.{\[]}
 278 \def\z{\[\0^b\1]}
 279 \def\dd{\slot{$\cdots$}}
 280 \def\vd{\slot{$\vdots$}}
 281 \def\rule{\noalign{\medskip\nointerlineskip}
 282 $\hrulefill$\cr
 283 \noalign{\nointerlineskip\medskip}}
 284
 285 \alik{
 286 \[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
 287 *~~ \z \dd \z\z\z \cr
 288 \rule
 289 \[x_{n-1}] \dd \[x_2] \[x_1] \[x_0] \cr
 290 \[x_{n-1}] \[x_{n-2}] \dd \[x_1] \[x_0] \. \cr
 291 \[x_{n-1}] \[x_{n-2}] \[x_{n-3}] \dd \[x_0] \. \. \cr
 292 \vd\vd\vd\vd\.\.\.\cr
 293 \[x_{n-1}] \dd \[x_2]\[x_1]\[x_0] \. \. \. \. \cr
 294 \rule
 295 \[r_{n-1}] \dd \[r_2] \[r_1] \[s_n] \dd \[s_3] \[s_2] \[s_1] \cr
 296 }
 297 Zde je výsledkem dokonce vektor všech částečných součtů:
 298 $s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{n-1}x_i$.
 299 \endlist
 300
 301 \:$\<Cmp>(x,y)$ -- paralelní porovnání dvou vektorů: $i$-tá složka výsledku je~1, pokud
 302 $x_i<y_i$, jinak~0.
 303
 304 \setbox0=\vbox{\hbox{~$x_{n-1}$}\hbox{~$y_{n-1}$}}
 305 \slotwd=\wd0
 306 \alik{
 307    \1 \[x_{n-1}] \1 \[x_{n-2}] \[\cdots] \1 \[x_1] \1 \[x_0]  \cr
 308 -~ \0 \[y_{n-1}] \0 \[y_{n-2}] \[\cdots] \0 \[y_1] \0 \[y_0]  \cr
 309 }
 310
 311 Ve~vektoru $x$ nahradíme prokládací nuly jedničkami a odečteme vektor~$y$.
 312 Ve~výsledku se tyto jedničky změní na~nuly právě u těch složek, kde $x_i < y_i$.
 313 Pak je již stačí posunout na~správné místo a okolní bity vynulovat a znegovat.
 314
 315 \:$\<Rank>(\alpha,x)$ -- spočítá, kolik složek vektoru~$x$ je menších než~$\alpha$:
 316 $$\<Rank>(\alpha,x) = \<Sum>(\<Cmp>(\<Replicate>(\alpha),x)).$$
 317
 318 \:$\<Insert>(\alpha,x)$ -- zatřídí hodnotu $\alpha$ do~setříděného vektoru~$x$:
 319
 320 Zde stačí pomocí operace \<Rank> zjistit, na~jaké místo novou hodnotu
 321 zatřídit, a~pak to pomocí bitových operací provést (\uv{rozšoupnout}
 322 existující hodnoty).
 323
 324 \:$\<Unpack>(\alpha)$ -- vytvoří vektor, jehož složky jsou bity zadaného čísla
 325 (jinými slovy proloží bity bloky $b$~nul).
 326
 327 Nejdříve číslo~$\alpha$ replikujeme, pak andujeme vhodnou bitovou maskou,
 328 aby v~$i$-té složce zůstal pouze $i$-tý bit a ostatní se vynulovaly,
 329 a pak provedeme $\<Cmp>$ s~vektorem samých nul.
 330
 331 \:$\<Unpack>_\varphi(\alpha)$ -- podobně jako předchozí operace, ale bity ještě
 332 prohází podle nějaké pevné funkce $\varphi$:
 333
 334 Stačí zvolit bitovou masku, která v~$i$-té složce ponechá právě $\varphi(i)$-tý bit.
 335
 336 \finalfix{\goodbreak}
 337
 338 \:$\<Pack>(x)$ -- dostane vektor nul a jedniček a vytvoří číslo, jehož bity
 339 jsou právě složky vektoru (jinými slovy škrtne nuly mezi bity):
 340
 341 Představíme si, že složky čísla jsou o~jeden bit kratší a provedeme \<Sum>.
 342 Například pro $n=4$ a $b=4$:
 343
 344 \setbox0=\hbox{$x_3$}
 345 \slotwd=\wd0
 346 \def\z{\[\0]}
 347
 348 \def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
 349 \def\.{\hphantom{\|}}
 350
 351 \alik{
 352 \|\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
 353 \|\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
 354 }
 355
 356 Jen si musíme dát pozor na~to, že vytvořený vektor s~kratšími složkami
 357 není korektně prostrkán nulami. Konstrukce \<Sum> pomocí modula proto
 358 nebude správně fungovat a místo $\1^b$ vygeneruje $\0^b$. To můžeme
 359 buď ošetřit zvlášť, nebo použít konstrukci přes násobení, které
 360 to nevadí.
 361
 362 \endlist
 363
 364 \>Nyní ještě několik operací s~normálními čísly. Chvíli předpokládejme,
 365 že pro~$b$-bitová čísla na~vstupu budeme mít k~dispozici $b^2$-bitový
 366 pracovní prostor, takže budeme moci používat vektory s~$b$ složkami
 367 po~$b$ bitech.
 368
 369 \itemize\ibull
 370
 371 \:$\#1(\alpha)$ -- spočítá jedničkové bity v~zadaném čísle.
 372
 373 Stačí provést \<Unpack> a následně \<Sum>.
 374
 375 \:$\<Permute>_\pi(\alpha)$ -- přehází bity podle zadané fixní permutace.
 376
 377 Provedeme $\<Unpack>_\pi$ a \<Pack> zpět.
 378
 379 \:$\<LSB>(\alpha)$ -- Least Significant Bit (pozice nejnižší jedničky):
 380
 381 Podobně jako v~rozcvičce nejdříve vytvoříme číslo, které obsahuje
 382 nejnižší jedničku a vpravo od~ní další jedničky, a~pak tyto jedničky
 383 posčítáme pomocí $\#1$:
 384
 385 \alik{
 386 \alpha&=                        \9\9\9\9\9\1\0\0\0\0\cr
 387 \alpha-1&=                      \9\9\9\9\9\0\1\1\1\1\cr
 388 \alpha\oplus(\alpha-1)&=        \0\9\9\9\0\1\1\1\1\1\cr
 389 }
 390
 391 \:$\<MSB>(\alpha)$ -- Most Significant Bit (pozice nejvyšší jedničky):
 392
 393 Z~\<LSB> pomocí zrcadlení (operací \<Permute>).
 394
 395 \endlist
 396
 397 \>Poslední dvě operace dokážeme spočítat i v~lineárním prostoru, například
 398 pro \<MSB> takto: Rozdělíme číslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$.
 399 Pak pro každý blok zjistíme, zda v~něm je aspoň jedna jednička, zavoláním
 400 $\<Cmp>(0,x)$. Pomocí \<Pack> z~toho dostaneme slovo~$y$ odmocninové
 401 délky, jehož bity indikují neprázdné bloky. Na~toto číslo zavoláme předchozí
 402 kvadratické \<MSB> a zjistíme index nejvyššího neprázdného bloku.
 403 Ten pak izolujeme a druhým voláním kvadratického algoritmu najdeme nejlevější
 404 jedničku uvnitř něj.\foot{Dopouštíme se drobného podvůdku -- vektorové operace
 405 předpokládaly prostrkané nuly a ty tu nemáme. Můžeme si je ale snadno pořídit
 406 a bity, které jsme nulami přepsali, prostě zpracovat zvlášť.}
 407
 408 \references
 409 \bye