From b208caff67c66cfa3e53da98c6d33c2c051c2b4e Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sun, 9 Oct 2016 18:52:45 +0200 Subject: Typesetting FFT code. --- math/fft.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'math/fft.cpp') diff --git a/math/fft.cpp b/math/fft.cpp index b234d4e..f09b7e3 100644 --- a/math/fft.cpp +++ b/math/fft.cpp @@ -1,6 +1,8 @@ // Laufzeit: O(n log(n)). -typedef complex cplx; // Eigene Implementierung ist noch deutlich schneller. -vector fft(const vector &a, bool inverse = 0) { // a.size() muss eine Zweierpotenz sein! +typedef complex cplx; // Eigene Implementierung ist schneller. + +// a.size() muss eine Zweierpotenz sein! +vector fft(const vector &a, bool inverse = 0) { int logn = 1, n = a.size(); vector A(n); while ((1 << logn) < n) logn++; @@ -20,14 +22,12 @@ vector fft(const vector &a, bool inverse = 0) { // a.size() muss ein A[j + s / 2 + k] = u - w * t; if (inverse) A[j + k] /= 2, A[j + s / 2 + k] /= 2; w *= ws; - } - } - } + }}} return A; } // Polynome: a[0] = a_0, a[1] = a_1, ... und b[0] = b_0, b[1] = b_1, ... -// Integer-Koeffizienten: Runde beim Auslesen der Koeffizienten: (int)round(a[i].real()) +// Bei Integern: Runde Koeffizienten: (int)round(a[i].real()) vector a = {0,0,0,0,1,2,3,4}, b = {0,0,0,0,2,3,0,1}; a = fft(a); b = fft(b); for (int i = 0; i < (int)a.size(); i++) a[i] *= b[i]; -- cgit v1.2.3