let fft =
let (+@) = Complex.add in
let (-@) = Complex.sub in
let ( *@) = Complex.mul in
let c1 = Complex.one in
fun a -> let n = Array.length a in 
  (let j = ref 0 in for i = 0 to n-2 do
     if i < !j then (let t = a.(!j) in (a.(!j) <- a.(i); a.(i) <- t));
      let m = ref (n/2) in while !m <= !j do j := !j - !m; m := !m/2 done;
         j := !j + !m done;
      let j = ref 1 in let b = ref (Complex.neg c1) in while !j<n do let w = ref c1 in
         for m = 0 to !j-1 do let i = ref m in while !i < n do 
            let t = !w *@ a.(!i + !j) in
               (a.(!i + !j) <- a.(!i) -@ t; a.(!i) <- a.(!i) +@ t);
            w := !w *@ !b; i := !i + !j + !j done done;
         j := !j + !j; b := Complex.sqrt !b done); a;;
         
let z = Complex.zero in fft [|z; z; z; z; z; z; z; Complex.one|];;