Commits

Aldo Culquicondor committed 1742904

Pasando a punteros

Comments (0)

Files changed (3)

     return ans-(n==(1u<<(ans-1))?1:0);
 }
 
-vector<complex<long double>> bitReverseCopy(vector<complex<long double>> &x) {
+complex<long double> * bitReverseCopy(complex<long double> *x, size_t n) {
     // O(n lg n)
-    size_t n = x.size(), b = numbits(n);
-    vector<complex<long double>> X(n);
+    size_t b = numbits(n);
+    auto X = new complex<long double> [n];
     for(size_t k=0; k<n; k++)
         X[rev(k, b)] = x[k];
     return X;
 }
 
-vector<complex<long double>> FFT(vector<complex<long double>> &x, const bool inv = 0) {
+complex<long double> * FFT(complex<long double> *x, size_t n, const bool inv) {
     // O(n lg n)
-    size_t n = x.size(), b = numbits(n);
-    if(n < (1u<<b)) {
-        // mirroring para completar la potencia de 2
-        size_t np = 1u<<b;
-        x.resize(np);
-        for(size_t j=0; j<np-n; j++)
-            x[n+j] = x[n-j-2];
-        n = np;
-    }
-    auto X = bitReverseCopy(x);
+    // Asumiendo n potencia de 2
+    size_t b = numbits(n);
+    auto X = bitReverseCopy(x, n);
     for(size_t s=1; s<=b; s++) {
         size_t m = 1<<s;
         auto Wm = exp(complex<long double>(0, (inv?1:-1)*2.0*PI/m));
         size_t k, j;
-#pragma omp parallel for default(none) shared(X,n,m,Wm) private(k,j)
+        complex<long double> w, t, u;
+#pragma omp parallel for default(none) shared(X,n,m,Wm) private(k,j,w,t,u)
         for(k=0; k<n; k+=m) {
             //Este bucle puede ser paralelizado
-            complex<long double> w(1, 0);
+            w = complex<long double> (1, 0);
             for(j=0; j<m/2; j++) {
-                auto t = w*X[k+j+m/2];
-                auto u = X[k+j];
+                t = w*X[k+j+m/2];
+                u = X[k+j];
                 X[k+j] = u+t;
                 X[k+j+m/2] = u-t;
                 w *= Wm;
         }
     }
     if(inv)
-        for(auto &Xi: X)
-            Xi /= n;
+        for(size_t i=0; i<n; i++)
+            X[i] /= n;
     return X;
 }
 
-vector<complex<long double>> FFT(vector<long double> x) {
-    size_t n = x.size();
-    vector<complex<long double>> xx(n);
+complex<long double> * FFT(long double *x, size_t n, const bool inv) {
+    auto *xx = new complex<long double> [n];
     for(size_t i=0; i<n; i++)
         xx[i] = complex<long double>(x[i], 0);
-    return FFT(xx);
+    auto XX = FFT(xx, n, inv);
+    delete xx;
+    return XX;
 }
 
-vector<complex<long double>> IFFT(vector<complex<long double>> &x) {
-    return FFT(x, 1);
+complex<long double> * IFFT(complex<long double> *x, size_t n) {
+    return FFT(x, n, 1);
 }
 #include <complex>
-#include <vector>
 
-using std::vector;
 using std::complex;
 
 #ifdef DEBUG
 
 size_t numbits(size_t);
 
-vector<complex<long double>> bitReverseCopy(vector<complex<long double>> &);
+complex<long double> * bitReverseCopy(complex<long double> *, size_t);
 
-vector<complex<long double>> FFT(vector<complex<long double>> &, const bool);
+complex<long double> * FFT(complex<long double> *, size_t, const bool inv = 0);
 
-vector<complex<long double>> FFT(vector<long double>);
+complex<long double> * FFT(long double *, size_t, const bool inv = 0);
 
-vector<complex<long double>> IFFT(vector<complex<long double>> &);
+complex<long double> * IFFT(complex<long double> *, size_t);
 int main() {
     size_t n;
     scanf("#%zu", &n);
-    vector<long double> x(n);
-    for(auto &xi: x)
-        scanf("%Lf", &xi);
-    auto X = FFT(x);
-    for(auto Xi: X)
-        printf("%Lf ", abs(Xi));
+    auto *x = new long double [n];
+    for(size_t i=0; i<n; i++)
+        scanf("%Lf", &x[i]);
+    auto X = FFT(x, n);
+    for(size_t i=0; i<n; i++)
+        printf("%Lf ", abs(X[i]));
     puts("");
 /*    auto x2  = IFFT(X);
     cout<<"\n";