Zaawansowane algorytmy i struktury danych/Wykład 4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 
== Abstrakt ==
 
== Abstrakt ==
  
Naturalna metoda dodawania dwóch wielomianów wymaga czasu <math>\Theta(n)</math>, natomiast prosty algorytm mnożenia dwóch wielomianów stopnia <math>n</math> wymaga czasu <math>\Theta(n^2)</math>. W wykładzie tym pokażemy, jak z wykorzystaniem szybkiej transformaty Fouriera (STF) wykonać wszystkie podstawowe operacje na wielomianach w czasie większym niż <math>\Theta(n)</math> o czynnik polilogarytmiczny. Na wykładzie pokażemy, jak dla wielomianów stopnia <math>n</math>:
+
Naturalna metoda dodawania dwóch wielomianów wymaga czasu <math>\Theta(n)</math>, natomiast prosty algorytm mnożenia dwóch wielomianów stopnia <math>n</math> wymaga czasu <math>\Theta(n^2)</math>. W wykładzie tym pokażemy, jak z wykorzystaniem Szybkiej Transformaty Fouriera (STF) wykonać wszystkie podstawowe operacje na wielomianach w czasie większym niż <math>\Theta(n)</math> o czynnik polilogarytmiczny. W ramach wykładu pokażemy, jak dla wielomianów stopnia <math>n</math>:
 
* mnożyć je w czasie <math>O(n \log n)</math>,
 
* mnożyć je w czasie <math>O(n \log n)</math>,
 
* dzielić wielomiany w czasie <math>O(n \log n)</math>.
 
* dzielić wielomiany w czasie <math>O(n \log n)</math>.
  
Natomiast jako ćwiczenie pozostanie nam pokazanie, jak wykorzystać te algorytmy do
+
Natomiast jako ćwiczenie pozostanie nam pokazanie, jak wykorzystać te algorytmy do:
 
* obliczania wielomianu interpolacyjnego w czasie <math>O(n \log^2 n)</math>,
 
* obliczania wielomianu interpolacyjnego w czasie <math>O(n \log^2 n)</math>,
 
* obliczania wartości wielomianu w <math>n</math> punktach w czasie <math>O(n \log^2 n)</math>.
 
* obliczania wartości wielomianu w <math>n</math> punktach w czasie <math>O(n \log^2 n)</math>.
Linia 11: Linia 11:
 
== Mnożenie wielomianów w punktach ==
 
== Mnożenie wielomianów w punktach ==
  
Niech <math>A(x) = \sum_{i=0}^{n-1} a_i x^i</math> i <math>B(x) = \sum_{i=0}^{n-1} b_i x^i</math> będą wielomianami stopnia <math>n</math> nad ciałem <math>F</math>. Wielomiany te możemy jednoznaczne reprezentować poprzez ich wartości w <math>n</math> punktach. Następujące twierdzenie zostało sformułowane w ramach wykładu z Metod Numerycznych.
+
Niech <math>A(x) = \sum_{i=0}^{n-1} a_i x^i</math> i <math>B(x) = \sum_{i=0}^{n-1} b_i x^i</math> będą wielomianami stopnia <math>n</math> nad ciałem <math>F</math>. Wielomiany te możemy jednoznaczne reprezentować poprzez ich wartości w <math>n</math> punktach. Następujące twierdzenie zostało sformułowane w ramach wykładu z Metod Numerycznych([[MN09#interpolacja_lagrangea|zobacz]]).
  
{{twierdzenie|[Twierdzenie o interpolacji wielomianów]|interpolacja|Dla dowolnego zbioru <math>n</math> par <math>X = \{(x_0, y_0), (x_1, y_1), \ldots, (x_{n-1},y_{n-1})\}</math> takiego, że wszystkie wartości <math>x_i</math> są parami różne, istnieje jedyny wielomian <math>C(x)</math> stopnia <math>n</math> taki, że <math>C(x_i) = y_i</math> dla <math>i = 0,1,\ldots, n-1.</math>
+
{{twierdzenie|1 [Twierdzenie o interpolacji wielomianów]|interpolacja|Dla dowolnego zbioru <math>n</math> par <math>X = \{(x_0, y_0), (x_1, y_1), \ldots, (x_{n-1},y_{n-1})\}</math> takiego, że wszystkie wartości <math>x_i</math> są parami różne, istnieje jedyny wielomian <math>C(x)</math> stopnia <math>n</math> taki, że <math>C(x_i) = y_i</math> dla <math>i = 0,1,\ldots, n-1.</math>
 
}}
 
}}
  
Linia 19: Linia 19:
 
Niech <math>X</math> będzie ustalonym zbiorem parami różnych punktów <math>x_0, \ldots, x_{2n-1} \in F</math>. Dla tego zbioru punktów możemy wyznaczyć zbiory wartości wielomianów:
 
Niech <math>X</math> będzie ustalonym zbiorem parami różnych punktów <math>x_0, \ldots, x_{2n-1} \in F</math>. Dla tego zbioru punktów możemy wyznaczyć zbiory wartości wielomianów:
  
 +
{{wzor2|1=
 +
<math>X_A = \{(x_0,A(x_0)), (x_1, A(x_1), \ldots, (x_{2n-1}, A(x_{2n-1}))\},</math>}}
  
<center>
+
{{wzor2|1=
<math>X_A = \{(x_0,A(x_0)), (x_1, A(x_1), \ldots, (x_{2n-1}, A(x_{2n-1}))\}</math>
+
<math>X_B = \{(x_0, B(x_0)), (x_1, B(x_1), \ldots, (x_{2n-1}, B(x_{2n-1}))\}.</math>
 +
}}
  
<math>X_B = \{(x_0, B(x_0)), (x_1, B(x_1), \ldots, (x_{2n-1}, B(x_{2n-1}))\}</math>
 
</center>
 
  
 +
Niech <math>C</math> będzie wynikiem mnożenia wielomianów <math>A</math> i <math>B</math>, mamy wtedy:
  
Niech <math>C</math> będzie wynikiem mnożenia wielomianów <math>A</math> i <math>B</math>, mamy wtedy
+
{{wzor2|1=<math>C(x_i) = A(x_i)\cdot B(x_i)</math>.}}
  
 +
Ponieważ stopień wielomianu <math>C</math> jest nie większy niż <math>2n</math>, to z [[ZASD Moduł 4#interpolacja| Twierdzenia o interpolacji]] zbiór wartości:
  
<center>
+
{{wzor2|1=
<math>C(x_i) = A(x_i)\cdot B(x_i)</math>.
+
<math>X_{A\cdot B} = \{(x_0, A(x_0)B(x_0)), (x_1, A(x_1)B(x_1), \ldots, (x_{2n-1}, A(x_{2n-1})B(x_{2n-1})) \}</math>,
</center>
+
}}
  
 
+
jednoznacznie wyznacza wielomian <math>A \cdot B</math>. Mając zbiory <math>X_A</math> i <math> X_B </math>, możemy wyznaczyć zbiór <math>X_C</math> w czasie <math>O(n)</math>. A następnie na jego podstawie znaleźć wielomian <math>C</math>. Procedura ta jest przedstawiona na następującym rysunku:
Ponieważ stopień wielomianu <math>C</math> jest nie większy niż <math>2n</math>, to z [[ZASD Moduł 4#interpolacja| Twierdzenia o interpolacji]] zbiór wartości
 
  
  
 
<center>
 
<center>
<math>X_{A\times B} = \{(x_0, A(x_0)B(x_0)), (x_1, A(x_1)B(x_1), \ldots, (2x_{n-1}, A(x_{2n-1})B(x_{2n-1})) \}</math>,
+
<flash>file=Zasd_ilustr_u.swf|width=600|height=450</flash>
</center>
 
 
 
jednoznacznie wyznacza wielomian <math>A \times B</math>. Mając zbiory <math>X_A</math> i <math>X_B</math>, możemy wyznaczyć zbiór <math>X_C</math> w czasie <math>O(n)</math>. Procedura ta jest przedstawiona na następującym rysunku:
 
 
 
 
 
<center>
 
<flash>file=Zasd_ilustr_u.swf|width=460|height=350</flash>
 
 
</center>
 
</center>
  
Linia 55: Linia 50:
 
== Szybka transformata Fouriera (STF) ==
 
== Szybka transformata Fouriera (STF) ==
  
Problem obliczania wartości wielomianu w <math>n</math> punktach i problem jego interpolacji rozwiążemy, wykorzystując szybką transformatę Fouriera. W poprzednim rozdziale nie zakładaliśmy nic na temat zbioru punktów <math>X</math>. Głównym pomysłem w konstrukcji algorytmu STF będzie właśnie wybór odpowiedniego zbioru punktów X tak, aby jak największa ilość wykonywanych obliczeń powtarzała się.
+
Problem obliczania wartości wielomianu w <math>n</math> punktach i problem jego interpolacji rozwiążemy, wykorzystując szybką transformatę Fouriera. W poprzednim rozdziale nie zakładaliśmy nic na temat zbioru punktów <math>X</math>. Głównym pomysłem w konstrukcji algorytmu STF będzie właśnie wybór odpowiedniego zbioru punktów <math>X</math> tak, aby jak największa ilość wykonywanych obliczeń powtarzała się.
  
Założymy, że chcemy obliczyć wartości wielomianu <math>A(x) = \sum_{i=0}^{n-1} a_i x^i</math> oraz <math>n</math> jest parzyste. Jeżeli <math>n</math> jest nieparzyste, to dodajemy na początek <math>A(x)</math> jednomian <math>0x^{n+1}</math> co nie zmienia nam wyniku działania algorytmu. Punkty <math>X_n = \{x_0,x_1,\ldots,x_{n-1}\}</math> zdefiniujemy w następujący sposób:
+
Założymy, że chcemy obliczyć wartości wielomianu <math>A(x) = \sum_{i=0}^{n-1} a_i x^i</math> oraz <math>n</math> jest parzyste. Jeżeli <math>n</math> jest nieparzyste, to dodajemy na początek <math>A(x)</math> jednomian <math>0x^{n+1}</math> co nie zmienia wyniku działania algorytmu. Punkty <math>X_n = \{x_0,x_1,\ldots,x_{n-1}\}</math> zdefiniujemy w następujący sposób:
  
 
+
{{wzor2|1=
<center>
 
 
<math>x_i = e^{\frac{2\pi i}{n}}</math>.
 
<math>x_i = e^{\frac{2\pi i}{n}}</math>.
</center>
+
}}
 
 
  
 
Dla wielomianu <math>A(x)</math> definiujemy dwa nowe wielomiany <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math> poprzez wybranie do nich współczynników <math>A(x)</math> o numerach odpowiednio parzystych i nieparzystych:
 
Dla wielomianu <math>A(x)</math> definiujemy dwa nowe wielomiany <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math> poprzez wybranie do nich współczynników <math>A(x)</math> o numerach odpowiednio parzystych i nieparzystych:
  
 
+
{{wzor2|1=
<center>
 
 
<math>A^{[0]}(x) = a_0 + a_2x + a_4x^2 + \ldots + a_{n-2}x^{\frac{n}{2}-1}</math>,
 
<math>A^{[0]}(x) = a_0 + a_2x + a_4x^2 + \ldots + a_{n-2}x^{\frac{n}{2}-1}</math>,
 +
}}
  
 +
{{wzor2|1=
 
<math>A^{[1]}(x) = a_1 + a_3x + a_5x^2 + \ldots + a_{n-1}x^{\frac{n}{2}-1}</math>.
 
<math>A^{[1]}(x) = a_1 + a_3x + a_5x^2 + \ldots + a_{n-1}x^{\frac{n}{2}-1}</math>.
</center>
+
}}
 
 
  
 
Wielomiany <math>A^{[0]}(x)</math> oraz <math>A^{[1]}(x)</math> są stopnia co najwyżej <math>\frac{n}{2}</math>. Co więcej zachodzi:
 
Wielomiany <math>A^{[0]}(x)</math> oraz <math>A^{[1]}(x)</math> są stopnia co najwyżej <math>\frac{n}{2}</math>. Co więcej zachodzi:
  
{{wzor|wzor_1|1|<math>A(x) = A^{[0]}(x^2) + x A^{[1]}(x^2)</math>}}
+
{{wzor|wzor_1|1|<math>A(x) = A^{[0]}(x^2) + x A^{[1]}(x^2).</math>}}
  
 
Widzimy teraz, że problem ewaluacji wielomianu <math>A(x)</math> w punktach <math>\omega_n^0, \omega_n^1,\ldots, \omega_n^{n-1}</math> sprowadza się do:
 
Widzimy teraz, że problem ewaluacji wielomianu <math>A(x)</math> w punktach <math>\omega_n^0, \omega_n^1,\ldots, \omega_n^{n-1}</math> sprowadza się do:
 
* ewaluacji wielomianów <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math> w punktach
 
* ewaluacji wielomianów <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math> w punktach
  
 
+
{{wzor2|1=
<center>
 
 
<math>X' =\{x_0^2, x_1^2, \ldots, x_{n-1}^2\} </math>.
 
<math>X' =\{x_0^2, x_1^2, \ldots, x_{n-1}^2\} </math>.
</center>
+
}}
 
 
 
 
* a następnie obliczenie wartości <math>A(x) </math>wyniku zgodnie ze wzorem [[ZASD Moduł 4#wzor_1|(1)]].
 
  
Zauważmy, że z definicji punktów $x_i$ mamy:
+
* a następnie obliczenie wartości <math>A(x)</math> zgodnie ze wzorem [[ZASD Moduł 4#wzor_1|(1)]].
  
 +
Zauważmy, że z definicji punktów <math>x_i</math> mamy:
  
<center>
+
{{wzor2|1=
 
<math>x_i^2 = \left(e^{\frac{2\pi i}{n}} \right)^2 = e^{\frac{2\pi i}{n/2}}</math>.
 
<math>x_i^2 = \left(e^{\frac{2\pi i}{n}} \right)^2 = e^{\frac{2\pi i}{n/2}}</math>.
</center>
+
}}
 
 
  
 
Możemy teraz zauważyć, że zachodzi <math>x_i^2 = x_{i+\frac{n}{2}}^2</math>, a więc <math>X' = X_{\frac{n}{2}}</math>. Udało nam się więc zredukować problem rozmiaru <math>n</math> - obliczenia wartości wielomianu <math>A(x)</math> stopnia <math>n</math> w <math>n</math> punktach do dwóch problemów rozmiaru <math>\frac{n}{2}</math> - obliczenia wartości wielomianów <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math> stopnia <math>\frac{n}{2}</math> w <math>\frac{n}{2}</math> punktach. Możemy teraz zastosować tę technikę rekurencyjnie, otrzymując następujący algorytm.
 
Możemy teraz zauważyć, że zachodzi <math>x_i^2 = x_{i+\frac{n}{2}}^2</math>, a więc <math>X' = X_{\frac{n}{2}}</math>. Udało nam się więc zredukować problem rozmiaru <math>n</math> - obliczenia wartości wielomianu <math>A(x)</math> stopnia <math>n</math> w <math>n</math> punktach do dwóch problemów rozmiaru <math>\frac{n}{2}</math> - obliczenia wartości wielomianów <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math> stopnia <math>\frac{n}{2}</math> w <math>\frac{n}{2}</math> punktach. Możemy teraz zastosować tę technikę rekurencyjnie, otrzymując następujący algorytm.
  
{{algorytm|Algorytm Szybkiej Transformaty Fouriera|algorytm_fft|
+
{{algorytm|Szybkiej Transformaty Fouriera|algorytm_fft|
 
3=
 
3=
 
  STF(<math>a = (a_0,\ldots,a_{n-1})</math>)
 
  STF(<math>a = (a_0,\ldots,a_{n-1})</math>)
Linia 122: Linia 111:
 
Algorytm ten najpierw oblicza SFT wielomianów <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math>, a następnie łączy te wyniki w celu wyliczenia SFT dla wielomianu <math>A(x)</math>. Przeanalizujmy teraz wykonanie pętli. Zauważmy najpierw, że w <math>k</math>-tym  kroku pętli mamy <math>\omega = \omega_n^k = e^{\frac{2\pi i k}{n}} = x_k.</math>. Czyli:
 
Algorytm ten najpierw oblicza SFT wielomianów <math>A^{[0]}(x)</math> i <math>A^{[1]}(x)</math>, a następnie łączy te wyniki w celu wyliczenia SFT dla wielomianu <math>A(x)</math>. Przeanalizujmy teraz wykonanie pętli. Zauważmy najpierw, że w <math>k</math>-tym  kroku pętli mamy <math>\omega = \omega_n^k = e^{\frac{2\pi i k}{n}} = x_k.</math>. Czyli:
  
 
+
{{wzor2|1=<math>
<center><math>
+
\begin{array}{r@{}c@{}l}
y_k = y_k^{[0]} + x_k y_k^{[1]} = A^{[0]}(e^{\frac{2\pi i k}{n/2}}) + x_k A^{[1]}(e^{\frac{2\pi i k}{n/2}}) =
+
y_k &=& y_k^{[0]} + x_k y_k^{[1]} = A^{[0]}(e^{\frac{2\pi i k}{n/2}}) + x_k A^{[1]}(e^{\frac{2\pi i k}{n/2}}) =
</math></center>
+
\\&=& A^{[0]} \left(\left(e^{\frac{2\pi i k}{n}}\right)^2\right) + x_k A^{[1]}\left(\left(e^{\frac{2\pi i k}{n}}\right)^2\right)=\\ &=& A^{[0]}(x_k^2) + x_k A^{[1]}(x_k^2) = A(x_k),
<center><math>
+
\end{array}
= A^{[0]} \left(\left(e^{\frac{2\pi i k}{n}}\right)^2\right) + x_k A^{[1]}\left(\left(e^{\frac{2\pi i k}{n}}\right)^2\right) = A^{[0]}(x_k^2) + x_k A^{[1]}(x_k^2) = A(x_k),
+
</math>}}
</math></center>
 
 
 
  
 
oraz
 
oraz
  
 
+
{{wzor2|1=<math>
<center><math>
+
\begin{array}{r@{}c@{}l}
y_{k+\frac{n}{2}} = y_k^{[0]} - x_k y_k^{[1]} = A^{[0]}(e^{\frac{2\pi i k}{n/2}}) - e^{\frac{2\pi i k}{n}} A^{[1]}(e^{\frac{2\pi i k}{n/2}}) =
+
y_{k+\frac{n}{2}} &=& y_k^{[0]} - x_k y_k^{[1]} = A^{[0]}(e^{\frac{2\pi i k}{n/2}}) - e^{\frac{2\pi i k}{n}} A^{[1]}(e^{\frac{2\pi i k}{n/2}}) =
</math></center>
+
\\&=& A^{[0]}(e^{\frac{2\pi i (k + n/2)}{n/2}}) + e^{\frac{2\pi i k + n/2}{n}} A^{[1]}(e^{\frac{2\pi i (k + n/2)}{n/2}})=\\ &=& A^{[0]}(x_{k + n/2}^2) + x_{k + n/2}^2 A^{[1]}(x_{k + n/2}^2) = A(x_{k+\frac{n}{2}}).
 
+
\end{array}
<center><math>
+
</math>}}
= A^{[0]}(e^{\frac{2\pi i (k + n/2)}{n/2}}) + e^{\frac{2\pi i k + n/2}{n}} A^{[1]}(e^{\frac{2\pi i (k + n/2)}{n/2}}) = A^{[0]}(x_{k + n/2}^2) + x_{k + n/2}^2 A^{[1]}(x_{k + n/2}^2) = A(x_{k+\frac{n}{2}}).
 
</math></center>
 
  
 
Gdzie w ostatniej równości skorzystaliśmy ze wzoru [[ZASD Moduł 4#wzor_1|(1)]]. Widzimy zatem, że algorytm poprawnie oblicza wartość STF dla wielomianu <math>A(x)</math>. Równanie rekurencyjne na czas działania procedury STF wygląda następująco:
 
Gdzie w ostatniej równości skorzystaliśmy ze wzoru [[ZASD Moduł 4#wzor_1|(1)]]. Widzimy zatem, że algorytm poprawnie oblicza wartość STF dla wielomianu <math>A(x)</math>. Równanie rekurencyjne na czas działania procedury STF wygląda następująco:
  
 
+
{{wzor2|1=
<center>
 
 
<math>T(n) =2 T(\frac{n}{2}) + \Theta(n) = \Theta(n \log n)</math>.
 
<math>T(n) =2 T(\frac{n}{2}) + \Theta(n) = \Theta(n \log n)</math>.
</center>
+
}}
  
 
Poniższa animacja przedstawia działanie algorytmu SFT wywołanego dla wielomianu <math>A(x) = x^3 + 2x^2 + 5x + 3</math>. Wartości wielomianu <math>A(x)</math> wyznaczone są z wartości wielomianów <math>A^{[0]}(x)</math> i
 
Poniższa animacja przedstawia działanie algorytmu SFT wywołanego dla wielomianu <math>A(x) = x^3 + 2x^2 + 5x + 3</math>. Wartości wielomianu <math>A(x)</math> wyznaczone są z wartości wielomianów <math>A^{[0]}(x)</math> i
Linia 153: Linia 137:
  
 
<flash>file=Zasd_ilustr_a.swf|height=500|width=600</flash>
 
<flash>file=Zasd_ilustr_a.swf|height=500|width=600</flash>
 
  
 
=== Odwrotna transformata Fouriera ===
 
=== Odwrotna transformata Fouriera ===
  
Aby zakończyć konstrukcję algorytmu dla szybkiego mnożenia wielomianów, pozostaje nam pokazanie, jak obliczyć wielomian interpolujący dla zbioru punktów <math>X_n</math>. Obliczenie wykonane w czasie szybkiej transformaty Fouriera możemy przedstawić w postaci macierzowej jako mnożenie macierzy przez wektor <math>(A(x_0), A(x_1), \ldots, A(x_{n-1}))^T = V_n (a_0, a_1, \ldots, a_{n-1})^T</math>, gdzie <math>V_n = V(x_0,\ldots,x_{n-1})</math> jest macierzą Vandermonde'a zawierającą potęgi <math>x_j</math>
+
Aby zakończyć konstrukcję algorytmu dla szybkiego mnożenia wielomianów, pozostaje nam pokazanie, jak obliczyć wielomian interpolujący dla zbioru punktów <math>X_n</math>. Obliczenie wykonane w czasie szybkiej transformaty Fouriera możemy przedstawić w postaci macierzowej jako mnożenie macierzy przez wektor <math>(A(x_0), A(x_1), \ldots, A(x_{n-1}))^T = V_n (a_0, a_1, \ldots, a_{n-1})^T</math>, gdzie <math>V_n = V(x_0,\ldots,x_{n-1})</math> jest macierzą Vandermonde'a zawierającą potęgi <math>x_j</math>:
 
 
  
<center>
+
{{wzor2|1=
 
<math>
 
<math>
 
\left(
 
\left(
Linia 172: Linia 154:
 
\right) =
 
\right) =
 
\left[
 
\left[
\begin{matrix}
+
\begin{array}{cccccc}
 
x_0^0 & x_0^1 & x_0^2 & x_0^3 & \cdots & x_0^{n-1} \\
 
x_0^0 & x_0^1 & x_0^2 & x_0^3 & \cdots & x_0^{n-1} \\
 
x_1^0 & x_1^1 & x_1^2 & x_1^3 & \cdots & x_1^{n-1} \\
 
x_1^0 & x_1^1 & x_1^2 & x_1^3 & \cdots & x_1^{n-1} \\
Linia 178: Linia 160:
 
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
 
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
 
x_{n-1}^0 & x_{n-1}^1 & x_{n-1}^2 & x_{n-1}^3 & \cdots & x_{n-1}^{n-1} \\
 
x_{n-1}^0 & x_{n-1}^1 & x_{n-1}^2 & x_{n-1}^3 & \cdots & x_{n-1}^{n-1} \\
\end{matrix}
+
\end{array}
 
\right]
 
\right]
 
 
\left(
 
\left(
 
\begin{matrix}
 
\begin{matrix}
Linia 189: Linia 170:
 
a_{n-1}
 
a_{n-1}
 
\end{matrix}
 
\end{matrix}
\right)
+
\right).
 
</math>
 
</math>
</center>
+
}}
 
 
  
 
Element macierzy <math>V(x_0,\ldots,x_{n-1})</math> dany jest jako
 
Element macierzy <math>V(x_0,\ldots,x_{n-1})</math> dany jest jako
  
 
+
{{wzor2|1=
<center>
 
 
<math>(V_n)_{j,k} = V(x_0,\ldots,x_{n-1})_{j,k} = x_j^k</math>.
 
<math>(V_n)_{j,k} = V(x_0,\ldots,x_{n-1})_{j,k} = x_j^k</math>.
</center>
+
}}
 
 
  
 
Korzystając z definicji zbioru <math>X_n</math>, otrzymujemy
 
Korzystając z definicji zbioru <math>X_n</math>, otrzymujemy
  
 
+
{{wzor2|1=
<center>
 
 
<math>V(x_0,\ldots,x_{n-1})_{j,k} = \left(e^{\frac{2\pi i j}{n}}\right)^k
 
<math>V(x_0,\ldots,x_{n-1})_{j,k} = \left(e^{\frac{2\pi i j}{n}}\right)^k
 
= e^{\frac{2\pi ijk}{n}}.</math>
 
= e^{\frac{2\pi ijk}{n}}.</math>
</center>
+
}}
  
 
W celu wykonania operacji odwrotnej do SFT, czyli obliczenia wielomianu interpolacyjnego, musimy wykonać mnożenie <math>V_n^{-1} (A(x_0), A(x_1), \ldots, A(x_{n-1}))^T</math>.
 
W celu wykonania operacji odwrotnej do SFT, czyli obliczenia wielomianu interpolacyjnego, musimy wykonać mnożenie <math>V_n^{-1} (A(x_0), A(x_1), \ldots, A(x_{n-1}))^T</math>.
  
{{lemat|||Niech macierz <math>W_n</math> będzie zdefiniowana jako
+
{{lemat|2||Macierz <math>W_n</math> zdefiniowana jako:
  
 
+
{{wzor2|1=<math>
<center><math>
 
 
\left(W_n\right)_{j,k} = \frac{1}{n} e^{\frac{-2\pi ijk}{n}},
 
\left(W_n\right)_{j,k} = \frac{1}{n} e^{\frac{-2\pi ijk}{n}},
</math></center>
+
</math>}}
  
 +
jest macierzą odwrotną do macierzy <math>V_n</math>.
 +
}}
  
jest macierzą odwrotną do macierzy <math>V_n</math>.
 
}
 
 
{{dowod|||Pokażemy, że <math>V_n W_n = I</math>. Rozważmy pozycję <math>(j,k)</math> macierzy <math>V_n W_n</math>:
 
{{dowod|||Pokażemy, że <math>V_n W_n = I</math>. Rozważmy pozycję <math>(j,k)</math> macierzy <math>V_n W_n</math>:
  
 
+
{{wzor2|1=<math>
<center><math>
 
 
\left(V_n W_n\right)_{j,k} = \sum_{l=0}^{n-1} \left(V_n\right)_{j,l} \left(W_n\right)_{l,k}
 
\left(V_n W_n\right)_{j,k} = \sum_{l=0}^{n-1} \left(V_n\right)_{j,l} \left(W_n\right)_{l,k}
 
=\sum_{l=0}^{n-1} e^{\frac{2\pi i j l}{n}} \frac{1}{n} e^{\frac{-2\pi i l k}{n}} =
 
=\sum_{l=0}^{n-1} e^{\frac{2\pi i j l}{n}} \frac{1}{n} e^{\frac{-2\pi i l k}{n}} =
 
\sum_{l=0}^{n-1} \frac{1}{n} e^{\frac{2\pi l(j-k)}{n}} =
 
\sum_{l=0}^{n-1} \frac{1}{n} e^{\frac{2\pi l(j-k)}{n}} =
</math></center>
+
</math>}}
 
 
  
 
Jeżeli <math>j=k</math>, to <math>e^{\frac{2\pi k(j-k)}{n}} = 1</math> i suma ta jest równa <math>1</math>. W przeciwnym przypadku możemy skorzystać ze wzoru na sumę szeregu geometrycznego:
 
Jeżeli <math>j=k</math>, to <math>e^{\frac{2\pi k(j-k)}{n}} = 1</math> i suma ta jest równa <math>1</math>. W przeciwnym przypadku możemy skorzystać ze wzoru na sumę szeregu geometrycznego:
  
 
+
{{wzor2|1=<math>
<center><math>
 
 
= \frac{1}{n} \frac{1 - e^{\frac{2\pi n(j-k)}{n}}}
 
= \frac{1}{n} \frac{1 - e^{\frac{2\pi n(j-k)}{n}}}
 
{1 - e^{\frac{2\pi (j-k)}{n}}} =
 
{1 - e^{\frac{2\pi (j-k)}{n}}} =
 
\frac{1}{n} \frac{1 - 1^{(j-k)}}
 
\frac{1}{n} \frac{1 - 1^{(j-k)}}
 
{1 - e^{\frac{2\pi (j-k)}{n}}} = 0.
 
{1 - e^{\frac{2\pi (j-k)}{n}}} = 0.
</math></center>
+
</math>}}
  
 
+
Czyli rzeczywiście <math>V_n W_n = I</math>.
Czyli rzeczywiście <math>V_n W_n = I</math>. \qed
 
 
}}
 
}}
  
Linia 254: Linia 226:
 
{{wzor|wzor_2|2|<math>A(x) = D(x) B(x)  + R(x),</math>}}
 
{{wzor|wzor_2|2|<math>A(x) = D(x) B(x)  + R(x),</math>}}
  
oraz stopień wielomianu <math>R(x)</math> jest ostro mniejszy niż <math>n</math>. Wielomian <math>D(x)</math> nazywamy {{def|wynikiem dzielenia|}, a wielomian <math>R(x)</math> to {{def|reszta z dzielenia|}. Pierwszy pomysł jaki się od razu nasuwa, to spróbować policzyć odwrotność wielomianu <math>B(x)</math> i przemnożenie przez tę odwrotność stronami tego równania. Niestety wielomiany nie mają odwrotności będących wielomianami. Jednak nie pozostajemy tutaj zupełnie bezradni. Możemy rozszerzyć naszą dziedzinę obliczeń tak aby zagwarantować istnienie pewnych odwrotności.
+
oraz stopień wielomianu <math>R(x)</math> jest ostro mniejszy niż <math>n</math>. Wielomian <math>D(x)</math> nazywamy '''wynikiem dzielenia''', a wielomian <math>R(x)</math> to '''reszta z dzielenia'''. Pierwszy pomysł jaki się od razu nasuwa, to spróbować policzyć odwrotność wielomianu <math>B(x)</math> i przemnożyć przez tę odwrotność strony tego równania. Niestety wielomiany nie mają odwrotności będących wielomianami. Jednak nie pozostajemy tutaj zupełnie bezradni. Możemy rozszerzyć naszą dziedzinę obliczeń tak aby zagwarantować istnienie pewnych odwrotności.
  
Obliczenia będziemy wykonywać nad zbiorem szeregów formalnych <math>F[[x]]</math> nad ciałem <math>F</math>, patrz [[Matematyka_dyskretna#szeregi formalne| Wykład z matematyki dyskretnej]]. Dla części elementów <math>F[[x]]</math> istnieją odwrotności. Elementy te są postaci <math>a + x A(x)</math>, gdzie <math>a\neq 0</math> i <math>A(x) \in F[[x]]</math>.
+
Obliczenia będziemy wykonywać nad zbiorem szeregów formalnych <math>F[[x]]</math> nad ciałem <math>F</math>, patrz [[Matematyka dyskretna 1/Wykład 7: Funkcje tworzące|Wykład z matematyki dyskretnej o funkcjach tworzących]]. Dla części elementów <math>F[[x]]</math> istnieją odwrotności. Elementy te są postaci <math>a + x A(x)</math>, gdzie <math>a\neq 0</math> i <math>A(x) \in F[[x]]</math>.
  
  
Linia 268: Linia 240:
 
{{cwiczenie||odwrotność_formalna|3=
 
{{cwiczenie||odwrotność_formalna|3=
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Czy umiesz obliczyć odwrotność dla szeregu <math>\sum_{j=0}^{\infty}jx^i</math>?
+
Czy umiesz obliczyć odwrotność dla szeregu <math>\sum_{j=0}^{\infty}(j+1)x^j</math>?
 
<div class="mw-collapsible-content" style="display:none">Odwrotność to <math>(1-x)^2</math>.</div>
 
<div class="mw-collapsible-content" style="display:none">Odwrotność to <math>(1-x)^2</math>.</div>
 
</div>
 
</div>
Linia 277: Linia 249:
 
wtedy:
 
wtedy:
  
 
+
{{wzor2|1=<math>
<center><math>
 
 
A^R(z) = D^R(z) B^R(z)  + z^{m-n-1}R^R(z) = B^R(z)D^R(z) \mod  z^{m-n-1},
 
A^R(z) = D^R(z) B^R(z)  + z^{m-n-1}R^R(z) = B^R(z)D^R(z) \mod  z^{m-n-1},
</math></center>
+
</math>}}
 
 
  
 
gdzie <math>A^R(z) = z^m A(\frac{1}{z})</math>, <math>D^R(z) = z^{m-n} D(\frac{1}{z})</math>, <math>B^R(z) = z^{n} B(\frac{1}{z})</math> i <math>R^R(z) = z^{n-1} R(\frac{1}{z})</math>, oznaczają wielomiany otrzymane poprzez odwrócenie kolejności współczynników. Z założenia, że <math>b_{n-1}\neq 0 </math> wiemy, że wielomian <math>B^R</math> ma odwrotność nad zbiorem szeregów formalnych. Możemy zapisać więc:
 
gdzie <math>A^R(z) = z^m A(\frac{1}{z})</math>, <math>D^R(z) = z^{m-n} D(\frac{1}{z})</math>, <math>B^R(z) = z^{n} B(\frac{1}{z})</math> i <math>R^R(z) = z^{n-1} R(\frac{1}{z})</math>, oznaczają wielomiany otrzymane poprzez odwrócenie kolejności współczynników. Z założenia, że <math>b_{n-1}\neq 0 </math> wiemy, że wielomian <math>B^R</math> ma odwrotność nad zbiorem szeregów formalnych. Możemy zapisać więc:
  
 
+
{{wzor|wzor_3|3|1=<math>
<center><math>
 
 
D^R(z) = A^R(x) \left(B^R(z)\right)^{-1} \mod z^{m-n-1}.
 
D^R(z) = A^R(x) \left(B^R(z)\right)^{-1} \mod z^{m-n-1}.
</math></center>
+
</math>}}
  
Zauważmy, że w celu wyznaczenia <math>D^R(z)</math> potrzebujemy tylko <math>m-n-1</math> wyrazów szeregu <math>\left(B^R(z)\right)^{-1}</math>. Wyższe wyrazy i tak znikną w wyniku wykonania mnożenia modulo <math>z^{m-n-1}</math>. Pozostało nam teraz tylko pokazać, jak wyznaczyć odwrotność dla szeregu formalnego. Algorytm ten przedstawiony jest poniżej
+
Zauważmy, że w celu wyznaczenia <math>D^R(z)</math> potrzebujemy tylko <math>m-n-1</math> wyrazów szeregu <math>\left(B^R(z)\right)^{-1}</math>. Wyższe wyrazy i tak znikną w wyniku wykonania mnożenia modulo <math>z^{m-n-1}</math>. Pozostało nam teraz tylko pokazać, jak wyznaczyć odwrotność dla szeregu formalnego. Algorytm ten przedstawiony jest poniżej.
  
  
{{algorytm|Obliczanie pierwszych <math>m</math> wyrazów odwrotnośći
+
{{algorytm|obliczania pierwszych <math>m</math> wyrazów odwrotnośći
 
szeregu formalnego|algorytm_odwrotność|
 
szeregu formalnego|algorytm_odwrotność|
 
3=
 
3=
  ODWROTNOŚĆ(A(x) = \sum_{i=0}^{n-1} a_i x^i, m)
+
  ODWROTNOŚĆ<math>(A(x) = \sum_{i=0}^{n-1} a_i x^i, m)</math>
 
   '''if''' <math>m=1</math> '''then''' '''return''' <math>1/a_0</math>
 
   '''if''' <math>m=1</math> '''then''' '''return''' <math>1/a_0</math>
 
   <math>A^{[0]}(x) = </math>ODWROTNOŚĆ<math>(A(x), \lfloor \frac{m}{2} \rfloor)</math>
 
   <math>A^{[0]}(x) = </math>ODWROTNOŚĆ<math>(A(x), \lfloor \frac{m}{2} \rfloor)</math>
Linia 304: Linia 273:
 
Obliczenie to jest poprawne, ponieważ:
 
Obliczenie to jest poprawne, ponieważ:
  
 
+
{{wzor2|1=<math>
<center><math>
 
 
\frac{1}{A(x)} - (A^{[0]}(x) -(A(x) A^{[0]}(x) -1) A^{[0]}(x)) = A(x)\left(\frac{1}{A(x)} - A^{[0]}(x)\right)^2,
 
\frac{1}{A(x)} - (A^{[0]}(x) -(A(x) A^{[0]}(x) -1) A^{[0]}(x)) = A(x)\left(\frac{1}{A(x)} - A^{[0]}(x)\right)^2,
</math></center>
+
</math>}}
 
 
 
 
a to jest równe wielokrotności <math>x^{2m}</math>, a więc jest także wielokrotnością <math>x^{n}</math>. Jeżeli wykorzystamy szybkie mnożenie wielomianów do obliczenia <math>(A^{[0]}(x) -(A(x) A^{[0]}(x) -1)A^{[0]}(x))</math>, to złożoność tego algorytmu wynosić będzie <math>O(n\log n)</math>. Możemy teraz skonstruować algorytm wykonujący dzielenie wielomianu <math>A(x)</math> przez wielomian <math>B(x)</math> w czasie <math>O(m \log m)</math>, gdzie <math>m</math> to stopień wielomianu <math>A(x)</math>.
 
  
 +
a to jest równe wielokrotności <math>x^{m}</math>. Jeżeli wykorzystamy szybkie mnożenie wielomianów do obliczenia <math>(A^{[0]}(x) -(A(x) A^{[0]}(x) -1)A^{[0]}(x))</math>, to złożoność tego algorytmu wynosić będzie <math>O(n\log n)</math>. Możemy teraz skonstruować algorytm wykonujący dzielenie wielomianu <math>A(x)</math> przez wielomian <math>B(x)</math> w czasie <math>O(m \log m)</math>, gdzie <math>m</math> to stopień wielomianu <math>A(x)</math>.
  
{{algorytm|Algorytm dzielenia wielomianów|algorytm_dzielenie|
+
{{algorytm|dzielenia wielomianów|algorytm_dzielenie|
 
3=
 
3=
  PODZIEL(A(x), B(x))
+
  PODZIEL<math>(A(x), B(x))</math>
 
   <math>A^R(z) = z^m A(\frac{1}{z})</math>
 
   <math>A^R(z) = z^m A(\frac{1}{z})</math>
 
   <math>B^R(z) = z^{n} B(\frac{1}{z})</math>
 
   <math>B^R(z) = z^{n} B(\frac{1}{z})</math>
Linia 324: Linia 290:
 
   '''return''' <math>(D(x), R(x))</math>
 
   '''return''' <math>(D(x), R(x))</math>
 
}}
 
}}
 +
 +
Poprawność tego algorytmu wynika wprost ze [[#wzor_3|wzoru (3)]], a jego złożoność wynosi naturalnie <math>O(n \log n)</math>.

Wersja z 15:46, 28 wrz 2006

Abstrakt

Naturalna metoda dodawania dwóch wielomianów wymaga czasu , natomiast prosty algorytm mnożenia dwóch wielomianów stopnia wymaga czasu . W wykładzie tym pokażemy, jak z wykorzystaniem Szybkiej Transformaty Fouriera (STF) wykonać wszystkie podstawowe operacje na wielomianach w czasie większym niż o czynnik polilogarytmiczny. W ramach wykładu pokażemy, jak dla wielomianów stopnia :

  • mnożyć je w czasie ,
  • dzielić wielomiany w czasie .

Natomiast jako ćwiczenie pozostanie nam pokazanie, jak wykorzystać te algorytmy do:

  • obliczania wielomianu interpolacyjnego w czasie ,
  • obliczania wartości wielomianu w punktach w czasie .

Mnożenie wielomianów w punktach

Niech i będą wielomianami stopnia nad ciałem . Wielomiany te możemy jednoznaczne reprezentować poprzez ich wartości w punktach. Następujące twierdzenie zostało sformułowane w ramach wykładu z Metod Numerycznych(zobacz).

Twierdzenie 1 [Twierdzenie o interpolacji wielomianów]

Dla dowolnego zbioru par takiego, że wszystkie wartości są parami różne, istnieje jedyny wielomian stopnia taki, że dla


Niech będzie ustalonym zbiorem parami różnych punktów . Dla tego zbioru punktów możemy wyznaczyć zbiory wartości wielomianów:


Niech będzie wynikiem mnożenia wielomianów i , mamy wtedy:

.

Ponieważ stopień wielomianu jest nie większy niż , to z Twierdzenia o interpolacji zbiór wartości:

,

jednoznacznie wyznacza wielomian . Mając zbiory i , możemy wyznaczyć zbiór w czasie . A następnie na jego podstawie znaleźć wielomian . Procedura ta jest przedstawiona na następującym rysunku:


<flash>file=Zasd_ilustr_u.swf|width=600|height=450</flash>


Jednak aby ostatecznie otrzymać szybszy algorytm niż algorytm naiwny, musimy pokazać jak rozwiązać problem obliczania wartości wielomianu w punktach w czasie szybszym niż . Podobnie musimy umieć obliczać wielomian interpolacyjny dla danego zbioru punktów.

Szybka transformata Fouriera (STF)

Problem obliczania wartości wielomianu w punktach i problem jego interpolacji rozwiążemy, wykorzystując szybką transformatę Fouriera. W poprzednim rozdziale nie zakładaliśmy nic na temat zbioru punktów . Głównym pomysłem w konstrukcji algorytmu STF będzie właśnie wybór odpowiedniego zbioru punktów tak, aby jak największa ilość wykonywanych obliczeń powtarzała się.

Założymy, że chcemy obliczyć wartości wielomianu oraz jest parzyste. Jeżeli jest nieparzyste, to dodajemy na początek jednomian co nie zmienia wyniku działania algorytmu. Punkty zdefiniujemy w następujący sposób:

.

Dla wielomianu definiujemy dwa nowe wielomiany i poprzez wybranie do nich współczynników o numerach odpowiednio parzystych i nieparzystych:

,
.

Wielomiany oraz są stopnia co najwyżej . Co więcej zachodzi:

     (1)

Widzimy teraz, że problem ewaluacji wielomianu w punktach sprowadza się do:

  • ewaluacji wielomianów i w punktach
.
  • a następnie obliczenie wartości zgodnie ze wzorem (1).

Zauważmy, że z definicji punktów mamy:

.

Możemy teraz zauważyć, że zachodzi , a więc . Udało nam się więc zredukować problem rozmiaru - obliczenia wartości wielomianu stopnia w punktach do dwóch problemów rozmiaru - obliczenia wartości wielomianów i stopnia w punktach. Możemy teraz zastosować tę technikę rekurencyjnie, otrzymując następujący algorytm.

Algorytm Szybkiej Transformaty Fouriera


 STF()
 if  nieparzyste then
   dodaj wyraz  do 
   zwiększ 
 if  then return a
 
 
 
 
 
 
 for k=0 to  do
   
   
   
 return y

Algorytm ten najpierw oblicza SFT wielomianów i , a następnie łączy te wyniki w celu wyliczenia SFT dla wielomianu . Przeanalizujmy teraz wykonanie pętli. Zauważmy najpierw, że w -tym kroku pętli mamy . Czyli:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} y_k &=& y_k^{[0]} + x_k y_k^{[1]} = A^{[0]}(e^{\frac{2\pi i k}{n/2}}) + x_k A^{[1]}(e^{\frac{2\pi i k}{n/2}}) = \\&=& A^{[0]} \left(\left(e^{\frac{2\pi i k}{n}}\right)^2\right) + x_k A^{[1]}\left(\left(e^{\frac{2\pi i k}{n}}\right)^2\right)=\\ &=& A^{[0]}(x_k^2) + x_k A^{[1]}(x_k^2) = A(x_k), \end{array} }

oraz

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} y_{k+\frac{n}{2}} &=& y_k^{[0]} - x_k y_k^{[1]} = A^{[0]}(e^{\frac{2\pi i k}{n/2}}) - e^{\frac{2\pi i k}{n}} A^{[1]}(e^{\frac{2\pi i k}{n/2}}) = \\&=& A^{[0]}(e^{\frac{2\pi i (k + n/2)}{n/2}}) + e^{\frac{2\pi i k + n/2}{n}} A^{[1]}(e^{\frac{2\pi i (k + n/2)}{n/2}})=\\ &=& A^{[0]}(x_{k + n/2}^2) + x_{k + n/2}^2 A^{[1]}(x_{k + n/2}^2) = A(x_{k+\frac{n}{2}}). \end{array} }

Gdzie w ostatniej równości skorzystaliśmy ze wzoru (1). Widzimy zatem, że algorytm poprawnie oblicza wartość STF dla wielomianu . Równanie rekurencyjne na czas działania procedury STF wygląda następująco:

.

Poniższa animacja przedstawia działanie algorytmu SFT wywołanego dla wielomianu . Wartości wielomianu wyznaczone są z wartości wielomianów i , a wartości tych wielomianów z wartości wielomianów , , i .

<flash>file=Zasd_ilustr_a.swf|height=500|width=600</flash>

Odwrotna transformata Fouriera

Aby zakończyć konstrukcję algorytmu dla szybkiego mnożenia wielomianów, pozostaje nam pokazanie, jak obliczyć wielomian interpolujący dla zbioru punktów . Obliczenie wykonane w czasie szybkiej transformaty Fouriera możemy przedstawić w postaci macierzowej jako mnożenie macierzy przez wektor , gdzie jest macierzą Vandermonde'a zawierającą potęgi :

Element macierzy dany jest jako

.

Korzystając z definicji zbioru , otrzymujemy

W celu wykonania operacji odwrotnej do SFT, czyli obliczenia wielomianu interpolacyjnego, musimy wykonać mnożenie .

Lemat 2

Macierz zdefiniowana jako:

jest macierzą odwrotną do macierzy .

Dowód

Pokażemy, że . Rozważmy pozycję macierzy :

Jeżeli , to i suma ta jest równa . W przeciwnym przypadku możemy skorzystać ze wzoru na sumę szeregu geometrycznego:

Czyli rzeczywiście .

End of proof.gif

Porównując postać macierzy oraz macierzy widzimy, że w celu obliczenia transformaty odwrotnej możemy użyć Algorytmu Szybkiej Transformaty Fouriera, musimy tylko zamienić linijkę na i podzielić otrzymany wynik przez .

Dzielenie wielomianów

W tej części wykładu skupimy się na problemie dzielenia dwóch wielomianów. Niech będzie wielomianem stopnia , a wielomianem stopnia . Zakładamy bez straty ogólności, że . W problemie dzielenia wielomianów chcemy obliczyć dwa wielomiany i takie, że

     (2)

oraz stopień wielomianu jest ostro mniejszy niż . Wielomian nazywamy wynikiem dzielenia, a wielomian to reszta z dzielenia. Pierwszy pomysł jaki się od razu nasuwa, to spróbować policzyć odwrotność wielomianu i przemnożyć przez tę odwrotność strony tego równania. Niestety wielomiany nie mają odwrotności będących wielomianami. Jednak nie pozostajemy tutaj zupełnie bezradni. Możemy rozszerzyć naszą dziedzinę obliczeń tak aby zagwarantować istnienie pewnych odwrotności.

Obliczenia będziemy wykonywać nad zbiorem szeregów formalnych nad ciałem , patrz Wykład z matematyki dyskretnej o funkcjach tworzących. Dla części elementów istnieją odwrotności. Elementy te są postaci , gdzie i .


Ćwiczenie

Czy umiesz obliczyć odwrotność dla szeregu ?

Ćwiczenie

Czy umiesz obliczyć odwrotność dla szeregu ?


Do wzoru (2) wstawmy , otrzymamy wtedy:

gdzie , , i , oznaczają wielomiany otrzymane poprzez odwrócenie kolejności współczynników. Z założenia, że wiemy, że wielomian ma odwrotność nad zbiorem szeregów formalnych. Możemy zapisać więc:

{{{3}}}     

Zauważmy, że w celu wyznaczenia potrzebujemy tylko wyrazów szeregu . Wyższe wyrazy i tak znikną w wyniku wykonania mnożenia modulo . Pozostało nam teraz tylko pokazać, jak wyznaczyć odwrotność dla szeregu formalnego. Algorytm ten przedstawiony jest poniżej.


Algorytm obliczania pierwszych wyrazów odwrotnośći szeregu formalnego


 ODWROTNOŚĆ
 if  then return 
 ODWROTNOŚĆ
 return 

Obliczenie to jest poprawne, ponieważ:

a to jest równe wielokrotności . Jeżeli wykorzystamy szybkie mnożenie wielomianów do obliczenia , to złożoność tego algorytmu wynosić będzie . Możemy teraz skonstruować algorytm wykonujący dzielenie wielomianu przez wielomian w czasie , gdzie to stopień wielomianu .

Algorytm dzielenia wielomianów


 PODZIEL
  
  
  ODWROTNOŚĆ
  
  
  
  return 

Poprawność tego algorytmu wynika wprost ze wzoru (3), a jego złożoność wynosi naturalnie .