Submission #2588836

---

Source Code Expand

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <complex.h>

#define K (8192)
double complex f[K], g[K], h[K];
#undef K

uint32_t bitrev32(uint32_t x)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16));
}

uint32_t bitrev(uint32_t x, int msbi) {
    return bitrev32(x) >> (msbi+1);
}

void fft (double complex f[], int K) {
    const int msbi =  __builtin_clz(K);
    for(int i=1; i<K; i<<=1) {
        const double complex w = cexp( -I * 2.0*M_PI / (i<<1) );
        for(int j=0; j<K; j+=i<<1) {
            double complex wn = 1;
            for(int k=0; k<i; k++) {
                const int ai = bitrev(j+k, msbi);
                const int bi = bitrev(i+j+k, msbi);

                const double complex a = f[ai], b = wn*f[bi];
                f[ai] = a + b;
                f[bi] = a - b;
                wn *= w;
            }
        }
    }
    for(int i=0; i<K; i++) {
        const int j = bitrev(i,msbi);
        if(j>=i) continue;
        const double complex t = f[i];
        f[i] = f[j];
        f[j] = t;
    }
    return;
}

void ifft (double complex f[], int K) {
    for(int i=0; i<K; i++)
        f[i] = conj(f[i]);
    fft(f, K);
    for(int i=0; i<K; i++)
        f[i] = conj(f[i]) / K;
}

void naive (double complex f[], int K) {
    double complex F[K];
    for(int i=0; i<K; i++) {
        F[i] = 0;
        for(int j=0; j<K; j++) {
            F[i] += f[j] * cexp( -I * 2.0*M_PI/K * i*j );
        }
    }
    memcpy(f, F, sizeof(F));
}

int main(void) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(h, 0, sizeof(h));

    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
#define K (8192)
        double a,b;
        scanf("%lf%lf", &a, &b);
        f[i] = a + 0 * I;
        g[i] = b + 0 * I;
    }

    fft(f, K);
    fft(g, K);

    for(int i=0; i<K; i++)
        h[i] = f[i] * g[i];

    ifft(h, K);

    for(int i=1; i<=2*n; i++)
        printf("%d\n", (int)round(creal(h[i])));
#undef K

    return 0;
}

Submission Info

Compile Error

./Main.cpp:9:16: error: expected initializer before ‘f’
 double complex f[K], g[K], h[K];
                ^
./Main.cpp:25:26: error: expected ‘,’ or ‘...’ before ‘f’
 void fft (double complex f[], int K) {
                          ^
./Main.cpp: In function ‘void fft(double)’:
./Main.cpp:26:37: error: ‘K’ was not declared in this scope
     const int msbi =  __builtin_clz(K);
                                     ^
./Main.cpp:28:30: error: expected initializer before ‘w’
         const double complex w = cexp( -I * 2.0*M_PI / (i<<1) );
                              ^
./Main.cpp:30:28: error: expected initializer before ‘wn’
             double complex wn = 1;
                            ^
./Main.cpp:35:38: error: expected initializer before ‘a’
                 const double complex a = f[ai], b = wn*f[bi];
                                      ^
./Main.cpp:36:17: error: ‘f’ was not declared in this scope
                 f[ai] = a + b;
                 ^
./Main.cpp:36:25: error: ‘a’ was not declared in ...