diff options
Diffstat (limited to 'math/fft.cpp')
| -rw-r--r-- | math/fft.cpp | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/math/fft.cpp b/math/fft.cpp index 8fe38e5..b234d4e 100644 --- a/math/fft.cpp +++ b/math/fft.cpp @@ -1,7 +1,6 @@ // 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) { +vector<cplx> fft(const vector<cplx> &a, bool inverse = 0) { // a.size() muss eine Zweierpotenz sein! int logn = 1, n = a.size(); vector<cplx> A(n); while ((1 << logn) < n) logn++; @@ -27,7 +26,8 @@ vector<cplx> fft(const vector<cplx> &a, bool inverse = 0) { return A; } -// Polynome: a_0, a_1, ... & b_0, b_1, ... +// 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()) vector<cplx> 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]; |