From 52ba871e0de9399f77da4b5b0d2c33a2dd6eb6a1 Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 18 Jan 2025 03:05:17 +0100 Subject: changes to bitwise convolutions - modify or/and transform to remove unnecessary reversal - or transform is now sum over subsets, add note about this - remove old sum over subsets DP --- content/math/math.tex | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'content/math/math.tex') 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} -- cgit v1.2.3