9-fft/9-fft.tex

   1 \def\scharfs{\char"19}
   2 \input lecnotes.tex
   3 \def\imply{\Rightarrow}
   4 \prednaska{9}{Fourierova transformace}{\vbox{\hbox{(K.Jakubec, M.Polák
   5         a~G.Ocsovszky,}\hbox{\ V.Tùma, M.Kozák)}}}
   6
   7 Násobení polynomù mù¾e mnohým pøipadat jako pomìrnì (algoritmicky) snadný
   8 problém. Asi ka¾dého hned napadne \uv{hloupý} algoritmus -- vezmeme
   9 koeficienty prvního polynomu a~vynásobíme ka¾dý se v¹emi koeficienty druhého
  10 polynomu a~pøíslu¹nì u~toho seèteme i~exponenty (stejnì jako to dìláme, kdy¾
  11 násobíme polynomy na~papíøe). Pokud stupeò prvního polynomu je $n$ a~druhého
  12 $m$, strávíme tím èas $\Omega(mn)$. Pro $m=n$ je to kvadraticky pomalé.
  13 Na~první pohled se mù¾e zdát, ¾e rychleji to prostì nejde (pøeci musíme
  14 v¾dy vynásobit \uv{ka¾dý s~ka¾dým}). Ve skuteènosti to ale rychleji fungovat
  15 mù¾e, ale k~tomu je potøeba znát trochu tajemný algoritmus FFT neboli {\I Fast
  16 Fourier Transform}.
  17
  18
  19 \ss{Trochu algebry na~zaèátek}
  20 Celé polynomy oznaèujeme velkými písmeny, jednotlivé èleny polynomù pøíslu¹nými
  21 malými písmeny (pø.: polynom $W$ stupnì $d$ má koeficienty $w_{0}, w_{1},
  22 w_{2},\ldots, w_{d}$).
  23
  24 Libovolný polynom $P$ stupnì (nejvý¹e) $d$ lze reprezentovat
  25 jednak jeho koeficienty, tedy èísly $p_{0}, p_{1}, \ldots ,p_{d}$, druhak
  26 i~pomocí hodnot:
  27
  28 \>{\bf Lemma:} Polynom stupnì nejvý¹e $d$ je jednoznaènì urèeò svými
  29 hodnotami v~$d+1$ rùzných bodech.
  30
  31 \>{\it Dùkaz:}
  32 Polynom stupnì $d$ má maximálnì $d$ koøenù (indukcí -- je-li
  33 $k$ koøenem $P$, pak lze $P$ napsat jako $(x-k)Q$ kde $Q$ je polynom stupnì
  34 o~jedna men¹í, pøitom polynom stupnì 1 má jediný koøen); uvá¾íme-li
  35 dva rùzné polynomy $P$ a~$Q$ stupnì $d$ nabývající v~daných bodech stejných
  36 hodnot, tak $P-Q$ je polynom stupnì maximálnì $d$, ka¾dé
  37 z $x_{0}\ldots x_{d}$ je koøenem tohoto polynomu $\imply$ spor, polynom stupnì
  38 $d$ má $d+1$ koøenù $\imply$ $P-Q$ musí být nulový polynom $\imply$ $P=Q$.
  39 \qed
  40 \medskip
  41
  42 Pov¹imnìme si jedné skuteènosti -- máme-li dva polynomy $A$ a~$B$ stupnì $d$
  43 a~body $x_{0}, \ldots, x_{n}$, dále polynom $C=A \cdot B$ (stupnì $2d$), pak
  44 platí $C(x_{j}) = A(x_{j}) \cdot B(x_{j})$ pro $j = 0,1,2, \ldots, n$. Toto
  45 èiní tento druhý zpùsob reprezentace polynomu velice atraktivním pro násobení
  46 -- máme-li $A$ i $B$ reprezentované hodnotami v $n \geq 2d+1$ bodech, pak
  47 snadno (v $\Theta(n)$) spoèteme takovou reprezentaci $C$.
  48 Problémem je, ¾e typicky máme polynom zadaný koeficienty, a~ne hodnotami
  49 v~bodech. Tím pádem potøebujeme nìjaký hodnì rychlý algorimtus (tj.
  50 rychlej¹í ne¾ kvadratický, jinak bychom si nepomohli oproti hloupému
  51 algoritmu) na~pøevod polynomu z jedné reprezentace do druhé a~zase zpìt.
  52
  53 \s{Idea, jak by mìl algoritmus pracovat:}
  54 \algo
  55 \:Vybereme $n\geq 2d+1$ bodù $x_{0}, x_{1}, \ldots , x_{n-1}$.
  56 \:V tìchto bodech vyhodnotíme polynomy $A$ a~$B$.
  57 \:Nyní ji¾ v~lineárním èase získáme hodnoty polynomu $C$ v~tìchto bodech:
  58         $C(x_i) = A(x_i)\cdot B(x_i)$
  59 \:Pøevedeme hodnoty polynomu $C$ na~jeho koeficienty.
  60 \endalgo
  61
  62 \>Je vidìt, ¾e klíèové jsou kroky 2 a~4.
  63 Celý trik spoèívá v~chytrém vybrání onìch bodù, ve kterých budeme polynomy
  64 vyhodnocovat -- zvolí-li se obecná $x_j$, tak se to rychle neumí, pro speciální
  65 $x_j$ ale uká¾eme, ¾e to rychle jde.
  66
  67 \ss{  Vyhodnocení polynomu metodou Rozdìl a~panuj (algoritmus FFT):}
  68 Mìjme polynom $P$ stupnì $\leq d$ a~chtìjme jej vyhodnotit v~$n$ bodech.
  69 Vybereme si body tak, aby byly spárované, èili $\pm x_{0}, \pm x_{1},
  70 \ldots , \pm x_{n/2-1} $. To nám výpoèet urychlí, proto¾e pak se druhé
  71 mocniny $x_{j}$ shodují s~druhými mocninami $-x_{j}$.
  72
  73 Polynom $P$ rozlo¾íme na~dvì èásti, první obsahuje èleny se sudými exponenty,
  74 druhá s~lichými:
  75 $$P(x) = (p_{0}x^{0} + p_{2}x^{2} + \ldots + p_{d-2}x^{d-2}) + (p_{1}x^{1} +
  76         p_{3}x^{3} + \ldots + p_{d-1}x^{d-1})$$
  77 \>se zavedením znaèení:
  78 $$P_s(t) = p_0t^0 + p_{2}t^{1} + \ldots + p_{d - 2}t^{d - 2\over 2}$$
  79 $$P_l(t) = p_1t^0 + p_3t^1 + \ldots + p_{d - 1}t^{d - 2\over 2}$$
  80
  81 \>bude $P(x) = P_s(x^{2}) + xP_l(x^{2})$ a~$P(-x) = P_s(x^{2}) -
  82 xP_l(x^{2})$. Jinak øeèeno, vyhodnocování polynomu $P$ v~$n$ bodech se nám
  83 smrskne na~vyhodnocení $P_s$ a~$P_l$ v~$n/2$ bodech -- oba jsou polynomy
  84 stupnì nejvý¹e $d/2$ a~vyhodnocujeme je v~$x^{2}$ (vyu¾íváme
  85 rovnosti $(x_{i})^{2} = (-x_{i})^{2}$).
  86
  87 \s{Pøíklad:}
  88 $3 + 4x + 6x^{2} + 2x^{3} + x^{4} + 10x^{5} = (3 + 6x^{2} + x^{4}) + x(4 +
  89 2x^{2} + 10x^{4})$.
  90
  91 Teï nám ov¹em vyvstane problém s~oním párováním -- druhá mocina pøece nemù¾e
  92 být záporná a~tím pádem u¾ v~druhé úrovni rekurze body spárované nebudou.
  93 Z~tohoto dùvodu musíme pou¾ít komplexní èísla -- tam druhé mocniny záporné býti
  94 mohou.
  95 % komplex
  96 \medskip
  97 \>{\bf Komplexní intermezzo}
  98 \itemize\ibull
  99 \def\i{i}       % ???; taky: ? sit, -> it
 100 {\parskip12pt
 101 \hfill{\bf Základní operace}
 102 \:Definice: ${\bb C} = \{a + b\i \mid a,b \in {\bb R}\}$
 103
 104 \:Sèítání: $(a+b\i)\pm(p+q\i) = (a\pm p) + (b\pm q)\i$.
 105 \vglue-8pt
 106 \qquad Pro $\alpha\in{\bb R}$ je $\alpha(a+b\i) = \alpha a + \alpha b\i$.
 107
 108 \:Komplexní sdru¾ení: $\overline{a+b\i} = a-b\i$.
 109 \vglue-8pt
 110 \qquad $\overline{\overline x} = x$, $\overline{x\pm y} = \overline{x} \pm
 111 \overline{y}$, $\overline{x\cdot y} = \overline x \cdot \overline y$, $x
 112 \cdot \overline x \in {\bb R}$.
 113
 114 \:Absolutní hodnota: $\vert x \vert = \sqrt{x\cdot\overline{x}}$, tak¾e $\vert
 115 a+b\i \vert = \sqrt{a^2+b^2}$.
 116
 117 \vglue-8pt
 118 \qquad Také $\vert \alpha x \vert = \vert \alpha\vert \cdot \vert x \vert$.
 119
 120 \:Dìlení: $x/y = (x\cdot \overline{y}) / (y \cdot \overline{y})$.
 121
 122 \hfill{\bf Gau{\scharfs}ova rovina a goniometrický tvar}
 123
 124 \:Komplexním èíslùm pøiøadíme body v~${\bb R}^2$: $a+b\i \leftrightarrow (a,b)$.
 125
 126 \:$\vert x\vert$ je vzdálenost od~bodu $(0,0)$.
 127
 128 \:$\vert x\vert = 1$ pro èísla le¾ící na~jednotkové kru¾nici ({\it komplexní
 129 jednotky\/}).
 130
 131 \vglue-8pt
 132 \qquad Pak platí $x=\cos\varphi + \i\sin\varphi$ pro nìjaké $\varphi\in\left[
 133 0,2\pi \right)$.
 134
 135 \:Pro libovolné $x\in{\bb C}$: $x=\vert x \vert \cdot (\cos\varphi(x) +
 136 \i\sin\varphi(x))$.
 137
 138 \vglue-8pt
 139 \qquad Èíslu $\varphi(x)\in\left[ 0,2\pi \right)$ øíkáme {\it argument\/}
 140 èísla~$x$, nìkdy znaèíme $\mathop{\rm arg} x$.
 141
 142 \:Navíc $\varphi({\overline{x}}) = -\varphi(x)$.
 143
 144 \hfill{\bf Komplexní èísla: Exponenciální tvar}
 145
 146 \:Eulerova formule: $e^{i\varphi} = \cos\varphi + \i\sin\varphi$.
 147
 148 \:Ka¾dé $x\in{\bb C}$ lze tedy zapsat jako $\vert x\vert \cdot e^{\i\cdot
 149 \varphi(x)}$.
 150
 151 \:Násobení: $xy = \left(\vert x\vert\cdot e^{\i\cdot\varphi(x)}\right) \cdot
 152         \left(\vert y\vert\cdot e^{\i\cdot\varphi(y)}\right) = \vert x\vert
 153         \cdot \vert y\vert \cdot e^{\i\cdot(\varphi(x) + \varphi(y))}$.
 154
 155 \vglue-8pt
 156 \qquad (absolutní hodnoty se násobí, argumenty sèítají)
 157
 158 \:Umocòování: $x^\alpha = \left(\vert x\vert\cdot e^{\i\cdot\varphi(x)}\right)^
 159         \alpha = {\vert x\vert}^\alpha\cdot e^{\i \alpha \varphi(x)}$.
 160
 161 \:Odmocòování: $\root n\of x = {\vert x\vert}^{1/n} \cdot e^{\i\cdot
 162 \varphi(x)/n}$.
 163
 164 \vglue-8pt
 165 \qquad pozor -- odmocnina není jednoznaèná: $1^4=(-1)^4=\i^4=(-\i)^4=1$.
 166
 167 \hfill{\bf Komplexní èísla: Odmocniny z~jednièky}
 168
 169 \:Je-li nìjaké $x\in{\bb C}$ $n$-tou odmocninou z~jednièky, musí platit:
 170 \vglue-8pt
 171 \qquad $\vert x \vert = 1$, tak¾e $x=e^{\i\varphi}$ pro nìjaké~$\varphi$,
 172 \vglue-8pt
 173 \qquad $e^{\i\varphi n} = \cos{\varphi n} + \i\sin\varphi n = 1$, proèe¾
 174 $\varphi n = 2k\pi$ pro nìjaké $k\in{\bb Z}$.
 175
 176 \:Z~toho plyne: $\varphi = 2k\pi/n$
 177 \vglue-8pt
 178 \qquad (pro $k=0,\ldots,n-1$ dostáváme rùzné $n$-té odmocniny).
 179
 180 \:Obecné odmocòování: $\root n \of x = {\vert x\vert}^{1/n} \cdot e^{\i\varphi
 181         (x)/n} \cdot u$, kde $u=\root n\of 1$.
 182
 183 \:Je-li $x$ odmocninou z 1, pak $\overline{x} = x^{-1}$ -- je toti¾ $1 = \vert
 184 x\cdot
 185         \overline{x}\vert = x\cdot \overline{x}$.
 186
 187 \vglue0pt minus4pt % hazel underfull vboxy
 188 \: $x$ je $k$-tá {\it primitivní} odmocnina z 1 $\equiv (\forall j<k)x^j
 189 \neq 1$, a $x^k = 1$
 190
 191 \hfill{\bf Komplexní èísla: Primitivní odmocniny}
 192
 193 \:Buï $\omega=e^{2\pi \i / k},\ k$ je sudé. Pak:
 194 \vglue-8pt
 195 \leftskip4em \parindent-1em
 196 $\star$ $\omega$ je $k$-tá primitivní odmocnina z 1 -- $j\cdot 2\pi \i / k = 1
 197         \Leftrightarrow j=k$.
 198 \vglue-8pt
 199 $\star$ pro $0\leq j<l<k$ je $\omega^j \neq \omega^l$, nebo» $\omega^l /
 200 \omega^j = \omega^{l-j} \neq 1$, proto¾e $l-j < k$ a $\omega$ je $k$-tá
 201 primitivní.
 202 \vglue-8pt
 203 $\star$ $\omega^{k/2} = -1$, proto¾e $(\omega^{k/2})^2 = 1$, a tedy
 204 $\omega^{k/2}$ je druhá odmocnina z 1 -- samotná 1 to ale být nemù¾e, $\omega$
 205         je primitivní.
 206 \vglue-8pt
 207 $\star$ $\omega^j = - \omega^{k/2 + j}$ -- pøímý dùsledek pøedchozího bodu, pro
 208 nás ale velice zajímavý; $\omega^0,\omega^1,\ldots,\omega^{k-1}$ jsou po dvou
 209 spárované.
 210 \vglue-8pt
 211 $\star$ $\omega^2$ je $k/2$-tá primitivní odmocnina z 1 -- dosazením.
 212 \vglue-8pt
 213
 214 }
 215 \endlist
 216 \medskip
 217 \>{\bf Konec intermezza}
 218 % end komplex
 219 \bigskip
 220 Vra»me se nyní k algoritmu. Z poslední èásti komplexního intermezza se zdá,
 221 ¾e by nemusel být ¹patný nápad zkusit vyhodnocovat polynom v mocninách
 222 $n$-té primitivní odmocniny z~jedné (tedy za $x_0,x_1,\ldots,x_{n-1}$
 223 z~pùvodního algoritmu zvolíme $\omega^0,\omega^1,\ldots,\omega^{n-1}$).
 224 Aby nám v¹e vycházelo pìknì, zvolíme $n$ jako mocninu dvojky.
 225
 226 \ss{Celý algoritmus bude vypadat takto:}
 227 \>FFT($P$, $ \omega$)
 228
 229 \>{\sl Vstup:} $p_{0}, \ldots , p_{n-1}$, koeficienty polynomu $P$ stupnì
 230 nejvý¹e $n-1$, a~$\omega$,
 231 $n$-tá primitivní odmocina z jedné.
 232
 233 \>{\sl Výstup:} Hodnoty polynomu v~bodech $1, \omega, \omega^{2}, \ldots ,
 234 \omega^{n - 1}$, èili èísla $P(1), P(\omega), P(\omega^{2}),$ $\ldots ,
 235 P(\omega^{n - 1})$.
 236
 237 \algo
 238 \:Pokud $n = 1$, vrátíme $p_{0}$ a~skonèíme.
 239 \:Jinak rozdìlíme $P$ èleny se sudými a lichými exponenty (jako v pùvodní
 240 my¹lence) a~rekurzivnì zavoláme FFT($P_s$, $\omega^{2}$) a~FFT($P_l$,
 241 $\omega^{2}$) -- $P_l$ i~$P_s$ jsou stupnì max. $n/2-1$, $\omega^2$ je
 242 $n/2$-tá primitivní odmocnina, a mocniny $\omega^2$ jsou stále po dvou
 243 spárované ($n$ je mocnina dvojky, a tedy i $n/2$ je sudé; popø. $n=2$ a je to
 244 zøejmé).
 245 \:Pro $j = 0, \ldots , n/2 - 1$ spoèítáme:
 246
 247 \:\qquad $P(\omega^{j}) = P_s(\omega^{2j}) + \omega^{j}\cdot P_l(\omega^{2j})$.
 248
 249 \:\qquad $P(\omega^{j+n/2})=P_s(\omega^{2j})-\omega^{j}\cdot P_l(\omega^{2j})$.
 250
 251 \endalgo
 252
 253
 254 \s{Èasová slo¾itost:}
 255 \>$T(n)=2T(n/2) + \Theta(n) \Rightarrow$ slo¾itost $\Theta(n \log n)$, jako
 256 MergeSort.
 257
 258
 259 Máme tedy algoritmus, který pøevede koeficienty polynomu na~hodnoty tohoto
 260 polynomu v~rùzných bodech. Potøebujeme ale také algoritmus, který doká¾e
 261 reprezentaci polynomu pomocí hodnot pøevést zpìt na~koeficienty polynomu.
 262 K~tomu nám pomù¾e podívat se na~ná¹ algoritmus trochu obecnìji.
 263
 264
 265 \s{Definice:}
 266 \>{\I Diskretní Fourierova transformace} $(DFT)$
 267 je zobrazení $f: { {\bb C} ^n} \rightarrow { {\bb C} ^n}$, kde $$y=f(x) \equiv
 268 \forall j \ y_{j} = \sum \limits ^{n-1}_{k=0} x_{k} \cdot \omega ^{jk}$$
 269 (DFT si lze mimo jiné pøedstavit jako funkci vyhodnocující polynom
 270 s~koeficienty $x_k$ v~bodech $\omega^j$). Takovéto zobrazení je lineární
 271 a~tedy popsatelné maticí $\Omega$ s~prvky $\Omega_{jk} = \omega^{jk}$.
 272 Chceme-li umìt pøevádìt z~hodnot polynomu na koeficienty, zajímá nás inverze
 273 této matice.
 274
 275
 276 \ss{Jak najít inverzní matici?}
 277 Znaème $\overline{\Omega}$ matici, její¾ prvky
 278 jsou komplexnì sdru¾ené odpovídajícím prvkùm $\Omega$, a vyu¾ijme následující
 279 lemma:
 280
 281 \ss{Lemma:}$\quad \Omega\cdot \overline{\Omega} = n\cdot E$.
 282
 283 \proof $$ (\Omega\cdot \overline{\Omega})_{jk} = \sum_{l=0}^{n-1} \omega^{jl}
 284 \cdot \overline{\omega^{lk}} = \sum \omega^{jl} \cdot \overline{\omega}^{lk} =
 285 \sum \omega^{jl} \cdot \omega^{-lk} = \sum \omega^{l(j-k)}\hbox{.}$$
 286 \itemize\ibull
 287 \:Pokud $j=k$, pak $ \sum \limits ^{n-1}_{l=0} (\omega ^{0}) ^{l} = n$.
 288
 289 \:Pokud $j\neq k$, pou¾ijeme vzoreèek pro souèet geometrické øady
 290 s kvocientem $\omega ^{(j-k) }$ a~dostaneme ${{\omega^{(j-k)n} -1} \over
 291 {\omega^{(j-k)} -1}} ={1-1 \over \neq 0} = 0$ (
 292 $\omega^{j-k} - 1$ je jistì $\neq 0$, nebo» $\omega$ je $n$-tá primitivní
 293 odmoncina a $j-k<n$).
 294 \endlist
 295 \qed
 296
 297
 298 \>Na¹li jsme inverzi:
 299 $\Omega({1 \over n} \overline{\Omega}) = {1 \over n}\Omega \cdot
 300 \overline{\Omega} = E$, \quad $\Omega^{-1}_{jk} = {1 \over n}\overline{\omega^
 301 {jk}} = {1 \over n}\omega^{-jk} = {1 \over n} {(\omega^{-1})}^{jk}$, \quad
 302 (pøipomínáme, $\omega^{-1}$ je $\overline{\omega}$).
 303
 304 Vyhodnocení polynomu lze provést vynásobením $\Omega$, pøevod do pùvodní
 305 reprezentace vynásobením $\Omega^{-1}$. My jsme si ale v¹imli chytrého
 306 spárování, a vyhodnocujeme polynom rychleji ne¾ kvadraticky (proto FFT,
 307 jako¾e {\it fast}, ne jako {\it fuj}). Uvìdomíme-li si, ¾e $\overline \omega =
 308 \omega^{-1}$ je také $n$-tá primitivní odmocnina z 1 (má akorát
 309 úhel s opaèným znaménkem), tak mù¾eme stejným trikem vyhodnotit i~zpìtný
 310 pøevod -- nejprve vyhodnotíme $A$ a $B$ v $\omega^j$, poté pronásobíme
 311 hodnoty a~dostaneme tak hodnoty polynomu $C=A\cdot B$, a pustíme na nì
 312 stejný algoritmus s~$\omega^{-1}$ (hodnoty $C$
 313 vlastnì budou v~algoritmu \uv{koeficienty polynomu}). Nakonec jen získané
 314 hodnoty vydìlíme $n$ a~máme chtìné koeficienty.
 315
 316 \s{Výsledek:} Pro $n= 2^k$ lze DFT na~${\bb C}^n$ spoèítat v~èase $\Theta(n
 317 \log n)$ a~DFT$^{-1}$ takté¾.
 318
 319 \s{Dùsledek:}
 320 Polynomy stupnì $n$ lze násobit v~èase $\Theta(n \log n)$:
 321 $\Theta(n \log n)$ pro vyhodnocení, $\Theta(n)$ pro vynásobení a~$\Theta(n
 322 \log n)$ pro pøevedení zpìt.
 323
 324 \s{Pou¾ití FFT:}
 325
 326 \itemize\ibull
 327
 328 \:Zpracování signálu -- rozklad na~siny a~cosiny o~rùzných frekvencích
 329 $\Rightarrow$ spektrální rozklad.
 330 \:komprese dat -- napøíklad formát JPEG.
 331 \:Násobení dlouhých èísel v~èase $\Theta(n \log n)$.
 332 \endlist
 333
 334 \s{Paralelní implementace FFT}
 335
 336 \figure{img.eps}{Pøíklad prùbìhu algoritmu na~vstupu velikosti 8}{3in}
 337
 338 Zkusme si prùbìh algoritmu FFT znázornit graficky (podobnì, jako jsme kreslili
 339 hradlové sítì). Na~levé stranì obrázku se nachází vstupní vektor $x_0,\ldots,x_{n-1}$
 340 (v~nìjakém poøadí), na~pravé stranì pak výstupní vektor $y_0,\ldots,y_{n-1}$.
 341 Sledujme chod algoritmu pozpátku: Výstup spoèítáme z~výsledkù \uv{polovièních}
 342 transformací vektorù $x_0,x_2,\ldots,x_{n-2}$ a $x_1,x_3,\ldots,x_{n-1}$.
 343 Èerné krou¾ky pøitom odpovídají výpoètu lineární kombinace $a+\omega^kb$,
 344 kde $a,b$ jsou vstupy krou¾ku a $k$~nìjaké pøirozené èíslo závislé na poloze
 345 krou¾ku. Ka¾dá z~polovièních transformací se poèítá analogicky z~výsledkù
 346 transformace velikosti $n/4$ atd. Celkovì výpoèet probíhá v~$\log_2 n$ vrstvách
 347 po~$\Theta(n)$ operacích.
 348
 349 Jeliko¾ operace na~ka¾dé vrstvì probíhají na sobì nezávisle, mù¾eme je poèítat
 350 paralelnì. Ná¹ diagram tedy popisuje hradlovou sí» pro paralelní výpoèet FFT
 351 v~èase $\Theta(\log n\cdot T)$ a prostoru $\O(n\cdot S)$, kde $T$ a~$S$ znaèí
 352 èasovou a prostorovou slo¾itost výpoètu lineární kombinace dvou komplexních èísel.
 353
 354 \s{Cvièení:} Doka¾te, ¾e permutace vektoru $x_0,\ldots,x_{n-1}$ odpovídá bitovému
 355 zrcadlení, tedy ¾e na pozici~$b$ shora se vyskytuje prvek $x_d$, kde~$d$ je
 356 èíslo~$b$ zapsané ve~dvojkové soustavì pozpátku.
 357
 358 \s{Nerekurzivní FFT}
 359
 360 Obvod z~pøedchozího obrázku také mù¾eme vyhodnocovat po~hladinách zleva doprava,
 361 èím¾ získáme elegantní nerekurzivní algoritmus pro výpoèet FFT v~èase $\Theta(n\log n)$
 362 a prostoru $\Theta(n)$:
 363
 364 \algo
 365 \algin $x_0,\ldots,x_{n-1}$
 366 \:Pro $j=0,\ldots,n-1$ polo¾íme $y_k\= x_{r(k)}$, kde $r$ je funkce bitového zrcadlení.
 367 \:Pøedpoèítáme tabulku $\omega^0,\omega^1,\ldots,\omega^{n-1}$.
 368 \:$b\= 1$ \cmt{velikost bloku}
 369 \:Dokud $b<n$, opakujeme:
 370 \::Pro $j=0,\ldots,n-1$ s~krokem~$2b$ opakujeme: \cmt{zaèátek bloku}
 371 \:::Pro $k=0,\ldots,b-1$ opakujeme: \cmt{pozice v~bloku}
 372 \::::$\alpha\=\omega^{nk/2b}$
 373 \::::$(y_{j+k},y_{j+k+b}) \= (y_{j+k}+\alpha\cdot y_{j+k+b}, y_{j+k}-\alpha\cdot y_{j+k+b})$.
 374 \::$b\= 2b$
 375 \algout $y_0,\ldots,y_{n-1}$
 376 \endalgo
 377
 378 \s{FFT v~koneèných tìlesech}
 379
 380 Nakonec dodejme, ¾e Fourierovu transformaci lze zavést nejen nad tìlesem
 381 komplexních èísel, ale i v~nìkterých koneèných tìlesech, pokud zaruèíme
 382 existenci primitivní $n$-té odmocniny z~jednièky. Napøíklad v~tìlese ${\bb
 383 Z}_p$ pro prvoèíslo $p=2^k+1$ platí $2^k=-1$, tak¾e $2^{2k}=1$
 384 a $2^0,2^1,\ldots,2^{2k-1}$ jsou navzájem rùzná, tak¾e èíslo~2 je~primitivní
 385 $2k$-tá odmocnina z~jedné. To se nám ov¹em nehodí pro algoritmus FFT, jeliko¾
 386 $2k$ bude málokdy mocnina dvojky.
 387
 388 Zachrání nás ov¹em algebraická vìta, která øíká, ¾e multiplikativní grupa\foot{To je
 389 mno¾ina v¹ech nenulových prvkù tìlesa s~operací násobení.}
 390 libovolného koneèného tìlesa je cyklická, tedy ¾e v¹echny nenulové prvky tìlesa lze
 391 zapsat jako mocniny nìjakého èísla~$g$ (generátoru). Napøíklad pro $p=2^{16}+1=65\,537$
 392 je jedním takovým generátorem èíslo~$3$. Jeliko¾ mezi èísly $g^1,g^2,\ldots,g^{p-1}$
 393 se musí ka¾dý nenulový prvek tìlesa vyskytnout právì jednou, je~$g$ primitivní
 394 $2^k$-tou odmocninou z~jednièky, tak¾e mù¾eme poèítat FFT pro libovolný vektor,
 395 jeho¾ velikost je mocnina dvojky men¹í nebo rovná $2^k$.\foot{Bli¾¹í prùzkum
 396 na¹ich úvah o~FFT dokonce odhalí, ¾e není ani potøeba tìleso. Postaèí libovolný
 397 komutativní okruh, ve~kterém existuje pøíslu¹ná primitivní odmocnina
 398 z~jednièky, její multiplikativní inverze (ta ov¹em existuje v¾dy, proto¾e
 399 $\omega^{-1} = \omega^{n-1}$) a multiplikativní inverze èísla~$n$. To nám
 400 poskytuje je¹tì daleko více volnosti ne¾ tìlesa, ale není snadné takové okruhy
 401 hledat.}
 402
 403 \bye