#include <stdio.h>
#include <complex.h>
#define LN 10
#define N (1<<LN)
typedef double _Complex c;
typedef long double _Complex cx;
void pc(c);

void fft(const int n, c a[n]){
  {int j=0, i; for(i=0; i<n-1; ++i) {
    if(i<j) {c t=a[j]; a[j]=a[i]; a[i]=t;}
    {int m=n/2; while(m<=j) {j -= m; m /= 2;} j += m;}}} 
  {int j=1, m; cx b=-1; while(j<n) {cx w = 1;
    for(m=0; m<j; ++m) {int i;
      for(i=m; i<n; i+=j+j)
        {c t = w*a[i+j]; a[i+j]=a[i]-t; a[i] += t;}
      w *= b;}
if(0) printf("z %e %e\n", creal(w+1), cimag(w+1));
    j *= 2; b = csqrtl(b);}}}

// tests
static double const ep = 4.5e-16;
#include <math.h>
void pc(c a){printf("%20.17lf + %20.17lfi\n",
    creal(a),  cimag(a));}
int main(){c A[N];
{int s = N; while(s--) {{int j=N; while(j--) A[j]=0;}
A[s]=1; fft(N, A);
if(0) {int j; for(j = 0; j<N; ++j) pc(A[j]);}
{ int j=N; while(j--) {double a = 2*(((s*j+512)&(N-1))-512)*3.14159265358979324/N;
  if(fabs(creal(A[j]) - cos(a)) > ep
  || fabs(cimag(A[j]) - sin(a)) > ep) {
    printf("er: %20.17f + %20.17fi %4d %4d\n    ", cos(a), sin(a), s, j);
     pc(A[j]);}}}}}
return 0;}

/* ep = 4.5e-16
er: -0.49822766697278154 +  0.86704624551569287i 1023  683
    -0.49822766697278198 +  0.86704624551569276i
er: -0.74913639452345904 + -0.66241577759017201i 1021  814
    -0.74913639452345948 + -0.66241577759017178i
er: -0.74913639452345904 +  0.66241577759017201i 1021  210
    -0.74913639452345948 +  0.66241577759017178i
er: -0.60061647938386864 +  0.79953726910790524i 1019  747
    -0.60061647938386908 +  0.79953726910790512i
er: -0.60061647938386864 + -0.79953726910790524i 1019  277
    -0.60061647938386908 + -0.79953726910790512i
er: -0.74913639452345904 + -0.66241577759017201i 1018  919
    -0.74913639452345948 + -0.66241577759017178i
er: -0.74913639452345904 +  0.66241577759017201i 1018  617
    -0.74913639452345948 +  0.66241577759017178i
er: -0.74913639452345904 + -0.66241577759017201i 1018  407
    -0.74913639452345948 + -0.66241577759017178i
er: -0.74913639452345904 +  0.66241577759017201i 1018  105
    -0.74913639452345948 +  0.66241577759017178i
er: -0.54532498842204613 +  0.83822470555483819i 1015  530
    -0.54532498842204657 +  0.83822470555483819i
er: -0.74913639452345904 +  0.66241577759017201i 1015   70
    -0.74913639452345948 +  0.66241577759017189i
er: -0.74913639452345904 +  0.66241577759017201i 1013  802
*/