diff options
Diffstat (limited to 'content/math/math.tex')
| -rw-r--r-- | content/math/math.tex | 6 |
1 files changed, 4 insertions, 2 deletions
diff --git a/content/math/math.tex b/content/math/math.tex index d59da54..fdf7081 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -321,6 +321,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{algorithm}
\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
+ \label{fft}
Multipliziert Polynome $A$ und $B$.
\begin{itemize}
\item $\deg(A \cdot B) = \deg(A) + \deg(B)$
@@ -328,14 +329,15 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: $\deg(A \cdot B) + 1$ haben.
Größe muss eine Zweierpotenz sein.
\item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))}
- \item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
+ \item \emph{or} Transform berechnet sum over subsets
+ $\rightarrow$ inverse für inclusion/exclusion
\end{itemize}
%\sourcecode{math/fft.cpp}
%\sourcecode{math/ntt.cpp}
\sourcecode{math/transforms/fft.cpp}
\sourcecode{math/transforms/ntt.cpp}
\sourcecode{math/transforms/bitwiseTransforms.cpp}
- Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
+ Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!)
\sourcecode{math/transforms/fftMul.cpp}
\end{algorithm}
|