From 47358081470c723dd27db55cf6499d775b805203 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Mon, 11 Jan 2016 18:02:21 +0100
Subject: Adding an FFT to be able to multiply two polynomials in time O(n log
 n).

---
 math/math.tex | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index b0f5144..acc85f6 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -26,7 +26,7 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 \subsubsection{Mod-Exponent über $\mathbb{F}_p$}
 \lstinputlisting{math/modExp.cpp}
 
-\subsection{LGS über $\mathbb{F}_p$}
+\subsubsection{LGS über $\mathbb{F}_p$}
 \lstinputlisting{math/lgsFp.cpp}
 
 \subsection{Binomialkoeffizienten}
@@ -50,6 +50,16 @@ Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu:
 	\item nimm Maximum aus gefundenem Maximalem und Allem\textbackslash Minimalem
 \end{enumerate}
 
+\subsection{Polynome \& FFT}
+Multipliziert Polynome $A$ und $B$.
+\begin{itemize}
+	\item $\deg(A * B) = \deg(A) + \deg(B)$
+	\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe $\deg(A * B) + 1$ haben.
+	Größe muss eine Zweierpotenz sein.
+	\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
+\end{itemize}
+\lstinputlisting{math/fft.cpp}
+
 \subsection{Kombinatorik}
 
 \subsubsection{Berühmte Zahlen}
-- 
cgit v1.2.3

