From 6a7442775d1b701f7fb471eb098cdac35eaacb63 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Tue, 12 Jan 2016 23:49:05 +0100
Subject: Adding an FFT and sample code to multiply two polynomials in O(n
 log(n)).

---
 math/fft.cpp |   2 ++
 tcr.pdf      | Bin 236823 -> 239278 bytes
 2 files changed, 2 insertions(+)

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();
diff --git a/tcr.pdf b/tcr.pdf
index b3a1c41..3be0561 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3