\documentstyle[12pt,A4,german]{article}
\begin{document}
\begin{center}
Multiplikation von Polynomen ---\\
nach ``Schulmethode'' und nach {\sc Karatsuba} 
\end{center}

Die ``landl"aufigen'' Methoden zur Erledigung allt"aglicher
algorithmischer Aufgaben, die ``Schulmethoden'' eben,
sind nicht in jedem Fall
auch die ``besten'' Methoden. Diese Erkenntnis ist vielleicht
nicht "uberraschend, aber sie l"asst sich schon an ganz einfachen
Problemen illustrieren.

Hier geht es um die Multiplikation von Polynomen - die Argumente treffen
aber mit leichten Modifikationen auch auf das Problem der Multiplikation von
ganzen Zahlen zu, die in Basis-Darstellung gegeben sind (allein das
Fehlen von ``"Ubertr"agen'' macht die Situation bei Polynomen noch
etwas einfacher).

Seien also $f = \sum_{i=0}^m f_i \, x^i$ und 
$g(x) = \sum_{j=0}^n g_j \, x^j$
Polynome mit Koeffizienten aus einem K"orper $K$ (oder einem
kommutativen Ring). Dabei sei $\deg f \leq m$, $\deg g \leq n$, 
es wird also nicht unterstellt, 
da"s $f_m \neq 0$ oder $g_n \neq 0$. F\"ur das
Produkt beider Polynome gilt
\[
f(x) \cdot g(x) =
\sum_{k=0}^{m+n} h_k \, x^k
~~\hbox{\rm mit}~~ h_k = \sum_{i+j=k} f_i \cdot g_j
\]
wobei in der Summe f"ur $h_k$ die Grenzen 
$\max(0,k-n) \leq i \leq \min (m,k)$ gelten.

Es soll nun der Frage nachgegangen werden,
wieviele Additionen und Multiplikationen im Koeffizientenberreich $K$
ben"otigt werden, um dieses Produkt zu berechnen.
Bei der "ublichen Methode zur Berechnung dieses Produkts,
also der Berechnung der $(h_k)_{0 \leq k \leq m+n}$
aus den $(f_i)_{0 \leq i \leq m}$ und
$(g_j)_{0 \leq j \leq n}$ sieht die Bilanz so aus:
\begin{itemize}
\item
$(m+1)(n+1)$ Multiplikationen in $K$, da jedes $f_i$ mit jedem $g_j$
multipliziert wird;
\item
$(m+1)(n+1) -(m+n+1) = mn $ Additionen in $K$, da aus den
$(m+1)(n+1)$ Produkten $f_i \cdot g_j$ die $m+n+1$ Koeffizienten
$h_k$ durch Addition gewonnen werden.
\end{itemize}

Eine {\em rekursive} Sicht der Schulmethode sieht so aus:
der Einfachheit halber seien $f$ und $g$ Polynome mit
$\deg f , \deg g < 2n$. $f$ und $g$ sind also durch jeweils $2n$
Koeffizienten bestimmt. Dann kann man schreiben:
\begin{eqnarray*}
f(x) &=& a(x) + x^n b(x) \\
g(x) &=& c(x) + x^n d(x)
\end{eqnarray*}
wobei $a(x),b(x),c(x),d(x)$ Polynome $\in K[x]$ vom Grad $< n$ sind,
also $a(x) = \sum_{i=0}^{n-1} f_i \, x^i$,
$ b(x) = \sum_{i=0}^{n-1} f_{n+i} \, x^i$, usw.
Schreiben wir nun $a$ statt $a(x)$ usw. 
Dann gilt also --- schulm"a"sig --
\begin{equation}\label{id_1}
f \cdot g = 
a \cdot c + x^n (a \cdot d + b \cdot c ) + x^{2n} b \cdot d
\end{equation}
und die {\em eine} Multiplikation $f \cdot g$
von zwei Polynomen mit Grad $< 2n$ ist reduziert auf die
{\em vier} Multiplikationen $a \cdot c , \,a \cdot d , \,b \cdot c$ und
$b \cdot d$ von Polynomen die jeweils einen Grad $<n$ haben. Dazu kommen
einige Additionen in $K$ ---
beachte: die Bereiche, wo $ a \cdot c$, 
$x^n (a \cdot d + b \cdot c )$ und $x^{2n} b \cdot d$ von $0$ verschiedene
Koeffizienten haben, "uberlappen sich!

Setzt man $m_1(n)$, bzw $a_1(n)$ f"ur die Anzahl der Multiplikationen
bzw. Additionen in $K$, die f"ur die Multiplikation zweier Polynome
vom Grad $<n$ durch {\em rekursive} Anwendung von (\ref{id_1}) 
ben"otigt werden, so ergibt sich
\begin{eqnarray*}
m_1(2n) &=& 4 \cdot m_1(n)~~~~,~~m_1(1)=1 \\
a_1(2n) &=& 4 \cdot a_1(n)+4n-3~~,~~a_1(1) =0
\end{eqnarray*}

{\sc Karatsuba}s Idee besteht darin, das Produkt $f \cdot g$ so zu schreiben:
\begin{equation}\label{id_2}
f \cdot g =
a \cdot c + x^n ((a+b)(c+d)-a \cdot c-b \cdot d) 
+ x^{2n} b \cdot d
\end{equation}
Man sieht: hier sind nur {\em drei} Multiplikationen von
Polynomen vom Grad $< n$ erforderlich: $a \cdot c$, $b \cdot d$
und $(a+b)(c+d)$. Dazu kommen noch Additionen in $K$: au"ser den
schon bei der ersten Methode erforderlichen Additionen m"ussen
hier noch $a+b$ und $c+d$ berechnet werden, dies ergibt $2n$ weitere
Additionen, und von $(a+b)(c+d)$ muss noch $a \cdot c + b \cdot d$
abgezogen werden, also nochmals $2n-1$ Additionen. (Subtraktionen werden
wie Additionen behandelt).

Setzt man $m_2(n)$, bzw $a_2(n)$ f"ur die Anzahl der Multiplikationen
bzw. Additionen in $K$, die f"ur die Multiplikation zweier Polynome
vom Grad $<n$ durch {\em rekursive} Anwendung von (\ref{id_2}) 
ben"otigt werden, so ergibt sich
\begin{eqnarray*}
m_2(2n) &=& 3 \cdot m_2(n)~~~~,~~m_2(1)=1 \\
a_2(2n) &=& 3 \cdot a_2(n)+8n-4~~,~~a_2(1) =0
\end{eqnarray*}

Der drastische Unterschied zwischen den beiden Methoden wird
am Vergleich von $m_1(n)$ und $m_2(n)$ deutlich (es wird der 
Einfachheit unterstellt, da"s $n$ eine Potenz von 2 ist):

\begin{eqnarray*}
m_1(n) = & n^2&\hbox{\rm falls}~n=2^k \\
m_2(n) = & n^{\log 3/\log 2}
\approx n^{1.585...}&\hbox{\rm falls}~n=2^k
\end{eqnarray*}

F"ur die Anzahl der Additionen ist die L"osung der
Rekursionsgleichungen f"ur $m_1(n)$ bzw $m_2(n)$
nicht so offensichlich, wobei man vermuten kann,
da"s das Resultat "ahnlich aussehen wird. 

Betrachten wir eine etwas allgemeinere Situation, um nicht
von eher unwesentlichen Details abgelenkt zu werden:

Sei eine Funktion $n \mapsto t(n)$ rekursiv definiert durch
\begin{equation}\label{rec}
t(2n) = a t(n) + b n + c ~~(n \geq 1)~~,~~t(1) = d
\end{equation}
wobei man sich bei den Argumenten von $t$ auf die Potenzen von $2$
beschr"ankt. Hierbei sind $a,b,c,d$ irgendwelche Konstanten.
Was kann man dann "uber das Verhalten von $n \mapsto t(n)$
sagen, falls $n$ gro"s wird?

Der "ubliche Ansatz zur Beantwortung dieser Frage besteht darin,
die Rekursion ``r"uckw"arts'' zu entfalten:
\begin{eqnarray*}
t(2^{m+1}) &=& a t(2^{m}) + b 2^{m} + c \\
&=&
a \left( a t(2^{m-1}) + b 2^{m-1} + c \right) + b 2^{m} + c \\
&=& \cdots
\end{eqnarray*}
Etwas eleganter kommt man zu dem gew"unschten Resultat, wenn man
die gesuchten Werte als Koeffizienten in
eine Potenzreihe packt:
\[
\tau(z) := \sum_{m \geq 0} t(2^m) \, z^m
\]
Die Rekursionsgleichung f"ur die $t(2^m)$ ist dann "aquivalent
zu einer Funktionalgleichung f"ur $\tau(z)$:
\begin{eqnarray*}
\tau(z) &=&
t(2^0) + \sum_{m \geq 0} t(2^{m+1}) \, z^{m+1} \\
&=&
d + \sum_{m \geq 0} \left( a \,t(2^m) +b\, 2^m+c \right) \, z^{m+1} \\
&=&
d + a\, z \sum_{m \geq 0} t(2^m) \, z^m 
+ b\, z \sum_{m \geq 0} 2^m \, z^m 
+ c \,z \sum_{m \geq 0} z^m \\
&=&
d + z \,a \tau(z) +  {b \,z \over 1-2z} +  { c\, z  \over 1-z} \\
\end{eqnarray*}
und diese lineare Gleichung kann man aufl"osen:
\[
\tau(z) =
{1 \over 1-a\,z}
\left(
d + { b\,z \over 1-2\,z} +  { c \,z \over 1-z} 
\right)
\]
Unter der Voraussetzung, da"s $a \neq 2$ und $a \neq 1$ ist, kann man
mittels Partialbruchzerlegung folgenderma"sen umformen. 
\begin{eqnarray*}
{1 \over 1-a\,z} \cdot {1 \over 1-2\,z} &=&
{1 \over a-2} \left( {a \over 1-a\,z} - {2 \over 1-2\,z} \right)\\
{1 \over 1-a\,z} \cdot {1 \over 1-z} &=&
{1 \over a-1} \left( {a \over 1-a\,z} - {1 \over 1-z}  \right)
\end{eqnarray*}
und damit erh"alt man
\[
\tau(z)
=
{d \over 1-a\,z}  
+{b \over a-2}\left({a\,z \over 1-a\,z} -{2\,z \over 1-2\,z}\right)
+{c \over a-1}\left({a\,z \over 1-a\,z}-{z \over 1-z}\right)
\]
Durch Koeffizientenvergleich bei Entwicklung der rechten Seite
ergibt sich also
\[
t(2^m) = \cases{
d & falls $m=0$ \cr
d\, a^m +{b \over a-2}(a^m-2^m) + {c \over a-1}(a^m-1)
& falls $m > 0 $ }
\]
Setzt man nun wieder $n$ f"ur $2^m$, so besagt dies
wegen $a^m = n^{\log_2 a}$:
\[
t(n) = k_1\, n^{\log_2 a} + k_2 \,n + k_3
\]
wobei $k_1, k_2, k_3$ von den $a,b,c,d$ abh"angen. 
($n$ durchl"auft hierbei die Potenzen von 2).

Die obige Herleitung schlie"st die F"alle $a=1$ und $a=2$
ausdr"ucklich aus! Es ist aber ganz instruktiv, sich anzusehen,
was in diesen F"allen geschieht. 

Zun"achst der Fall $a=2$. Dann gilt
\[
\tau(z)
=
{d \over 1-2\, z}  
+ {b\,z \over (1-2\,z)^2} + 
{2\,c\,z \over 1-2\,z} - {c\,z \over 1-z}
\]
Wegen
\[
{1 \over (1-z)^2} =
\sum_{m \geq 0} (m+1)\,z^m
\]
gilt also per Koeffizientenvergleich f"ur $m \geq 1$:
\[
t(2^m)
=
d\, 2^m + b \,m \,2^{m-1} + c \,2^m - c 
\]
Ersetzt man hier $2^m$ wieder durch $n$, so erh"alt man 
\[
t(n) = k_1 \, n \,  \log_2 n  + k_2 \, n + k_3
\]
und erkennt das f"ur viele klassische 
{\em divide-and-conquer}-Situationen
typische ``$n \,\log n$-Verhalten''.

Nun noch der Fall $a=1$. Hier gilt
\begin{eqnarray*}
\tau(z) & = & {1 \over 1-z} \left(
d + {b\,z \over 1 - 2\,z } + {c \,z \over 1-z}  \right)\\
&=&
{ d - b\,z \over 1-z} + {2\,b\,z \over 1-2\,z} + {c\,z \over (1-z)^2}
\end{eqnarray*}
und dies f"uhrt zu
\[t(2^m) =
d-b+2^m\,b+c\,m
\]
oder, wieder mit $n$ an Stelle von $2^m$,
\[
t(n) = k_1 \,n + k_2 \log\,n + k_3
\]
mit $k_1=b, k_2=c, k_3=d-b$.

Man erkennt, da"s die L"osungen der Rekursion (\ref{rec}),
je nach Gr"o"se von $a$, 
drei wesentlich unterschiedliche Verhaltensweisen zeigen:
\begin{itemize}
\item
Falls $a>2$ ist, dominiert der Term $k_1 \, n^{\log_2 a}$ ---
in der Sprache der Asymptotik ist
$t(n) \in \Theta(n^{\log_2 a})$
\item
Falls $a=2$ ist, dominiert der Term $k_1 \, n \, \log_2 \, n$,
es gilt $t(n) \in \Theta(n\, \log\,n)$
\item
Falls $a<2$ ist, dominiert der lineare Anteil, d.h.
$t(n) \in \Theta(n)$
\end{itemize}
Diese Dreiteilung ist typisch f"ur {\em divide-and-conquer} Situationen,
die durch Rekursionsgleichungen vom Typ
\[
t(a \, n) = b \, t(n) + f(n)
\]
beschrieben werden.
\end{document}