From f4dafa64e27e63d8cde5adcfbfa98e2a30fb7504 Mon Sep 17 00:00:00 2001
From: Noobie99 <noob999noob999@gmail.com>
Date: Mon, 5 Feb 2024 22:23:53 +0100
Subject: renamed ntt and bitwiseConv function + more multiply functions

---
 math/transforms/bitwiseTransforms.cpp |   2 +-
 math/transforms/multiply.cpp          |  12 ------------
 math/transforms/multiplyBitwise.cpp   |   8 ++++++++
 math/transforms/multiplyFFT.cpp       |  12 ++++++++++++
 math/transforms/multiplyNTT.cpp       |   8 ++++++++
 math/transforms/ntt.cpp               |   2 +-
 tcr.pdf                               | Bin 667072 -> 667178 bytes
 7 files changed, 30 insertions(+), 14 deletions(-)
 delete mode 100644 math/transforms/multiply.cpp
 create mode 100644 math/transforms/multiplyBitwise.cpp
 create mode 100644 math/transforms/multiplyFFT.cpp
 create mode 100644 math/transforms/multiplyNTT.cpp

diff --git a/math/transforms/bitwiseTransforms.cpp b/math/transforms/bitwiseTransforms.cpp
index 7d1f80d..28561da 100644
--- a/math/transforms/bitwiseTransforms.cpp
+++ b/math/transforms/bitwiseTransforms.cpp
@@ -1,4 +1,4 @@
-void fft(vector<ll>& a, bool inv = false) {
+void bitwiseConv(vector<ll>& a, bool inv = false) {
 	int n = sz(a);
 	for (int s = 1; s < n; s *= 2) {
 		for (int i = 0; i < n; i += 2 * s) {
diff --git a/math/transforms/multiply.cpp b/math/transforms/multiply.cpp
deleted file mode 100644
index 59c394e..0000000
--- a/math/transforms/multiply.cpp
+++ /dev/null
@@ -1,12 +0,0 @@
-vector<ll> mul(vector<ll>& a, vector<ll>& b) {
-	int n = 1 << (__lg(sz(a) + sz(b)) + 1);
-	vector<cplx> a2(all(a)), b2(all(b));
-	a2.resize(n), b2.resize(n);
-	fft(a2), fft(b2);
-	for (int i=0; i<n; i++) a2[i] *= b2[i];
-	fft(a2, true);
-
-	vector<ll> ans(n);
-	for (int i=0; i<n; i++) ans[i] = llround(a2[i].real());
-	return ans;
-}
diff --git a/math/transforms/multiplyBitwise.cpp b/math/transforms/multiplyBitwise.cpp
new file mode 100644
index 0000000..0fa671c
--- /dev/null
+++ b/math/transforms/multiplyBitwise.cpp
@@ -0,0 +1,8 @@
+vector<ll> mul(vector<ll> a, vector<ll> b) {
+	int n = 1 << (__lg(max(sz(a), sz(b)) - 1) + 1);
+	a.resize(n), b.resize(n);
+	bitwiseConv(a), bitwiseConv(b);
+	for (int i=0; i<n; i++) a[i] *= b[i]; // MOD?
+	bitwiseConv(a, true);
+	return a;
+}
diff --git a/math/transforms/multiplyFFT.cpp b/math/transforms/multiplyFFT.cpp
new file mode 100644
index 0000000..0022d1f
--- /dev/null
+++ b/math/transforms/multiplyFFT.cpp
@@ -0,0 +1,12 @@
+vector<ll> mul(vector<ll>& a, vector<ll>& b) {
+	int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1);
+	vector<cplx> a2(all(a)), b2(all(b));
+	a2.resize(n), b2.resize(n);
+	fft(a2), fft(b2);
+	for (int i=0; i<n; i++) a2[i] *= b2[i];
+	fft(a2, true);
+
+	vector<ll> ans(n);
+	for (int i=0; i<n; i++) ans[i] = llround(a2[i].real());
+	return ans;
+}
diff --git a/math/transforms/multiplyNTT.cpp b/math/transforms/multiplyNTT.cpp
new file mode 100644
index 0000000..806d124
--- /dev/null
+++ b/math/transforms/multiplyNTT.cpp
@@ -0,0 +1,8 @@
+vector<ll> mul(vector<ll> a, vector<ll> b) {
+	int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1);
+	a.resize(n), b.resize(n);
+	ntt(a), ntt(b);
+	for (int i=0; i<n; i++) a[i] = a[i] * b[i] % mod;
+	ntt(a, true);
+	return a;
+}
diff --git a/math/transforms/ntt.cpp b/math/transforms/ntt.cpp
index 18d5bd8..ca605d3 100644
--- a/math/transforms/ntt.cpp
+++ b/math/transforms/ntt.cpp
@@ -1,6 +1,6 @@
 constexpr ll mod = 998244353, root = 3;
 
-void fft(vector<ll>& a, bool inv = false) {
+void ntt(vector<ll>& a, bool inv = false) {
 	int n = sz(a);
 	auto b = a;
 	ll r = inv ? powMod(root, mod - 2, mod) : root;
diff --git a/tcr.pdf b/tcr.pdf
index 6404502..e7330c0 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3