#include <math.h>
#include "misc.h"
#include "fft.h"
C it(C w){C r; __real__ r = - __imag__ w;
   __imag__ r = __real__ w; return r;}
C Sqrt(C x){
R A = __real__ x, B = __imag__ x;
if(A < 0) return it(Sqrt(-x));
{R r = sqrt((A + sqrt(A*A + B*B))/2);
return r + it(B/(2*r));}}

void fft(c a[], const int n){
  {int j=0; for(int 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; C b=-1; while(j<n) {C w = 1;
    for(int m=0; m<j; ++m) {
      for(int i=m; i<n; i+=j+j)
        {C t = w*a[i+j]; a[i+j]=a[i]-t; a[i] += t;}
      w *= b;}
    j *= 2; b = Sqrt(b);}}}