\begin{slide}{Multiplikation}

$[x_0,\ldots] \cdot  [y_0,\ldots]$,
  \begin{itemize}
  \item Schulmethode:
    $x_0 \cdot y + 2\cdot [x_1,\ldots] \cdot y$ rekursiv

  \item Überläufe im Resultat früh erkennen,
    nur mit nötigen Stellen rechnen
  \item Karatsuba-Multiplikation:

    $(p + qB)(r + sB) = pr + \underbrace{(ps+qr)}_{=t}B + qsB^2$

    berechne $t = (p+q)(r+s) - pr - qs$ mit nur 3 Multiplikationen. 
  \end{itemize}
SAT-Formeln für binäre Multiplikation sind sehr schwer:
Resultatbit $k$ hängt von \emph{allen} 
Eingabebits $0,\dots,k$ ab.
\end{slide}
