From 52ba871e0de9399f77da4b5b0d2c33a2dd6eb6a1 Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
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

