Adding an FFT and sample code to multiply two polynomials in O(n log(n)).

1 files changed, 2 insertions, 0 deletions

diff --git a/math/fft.cpp b/math/fft.cpp
index 89018c5..8fe38e5 100644
--- a/math/fft.cpp
+++ b/math/fft.cpp
@@ -1,3 +1,5 @@
+// Laufzeit: O(n log(n)).
+typedef complex<double> cplx; // Eigene Implementierung ist noch deutlich schneller.
 // s.size() muss eine Zweierpotenz sein!
 vector<cplx> fft(const vector<cplx> &a, bool inverse = 0) {
 	int logn = 1, n = a.size();