Simple OCaml implementation of Inverse Discrete Fourier Transform.

idft.ml

type complex = {re: float; im: float}

let complex_add a b = {re = a.re +. b.re; im = a.im +. b.im}
let complex_mul a b = {re = a.re *. b.re -. a.im *. b.im; im = a.re *. b.im +. a.im *. b.re}
let complex_exp theta = {re = cos theta; im = sin theta}

let idft x =
  let n_total = Array.length x in
  let x_n n =
    let sum = ref {re = 0.0; im = 0.0} in
    for k = 0 to n_total - 1 do
      let e = complex_exp (2.0 *. Float.pi *. float_of_int k *. float_of_int n /. float_of_int n_total) in
      sum := complex_add !sum (complex_mul x.(k) e)
    done;
    {re = !sum.re /. float_of_int n_total; im = !sum.im /. float_of_int n_total}
  in
  Array.init n_total x_n

(* example usage *)
let () =
  let freq_domain = [|{re = 10.0; im = 0.0}; {re = -2.0; im = 2.0}; {re = -2.0; im = 0.0}; {re = -2.0; im = -2.0}|] in
  let time_domain = idft freq_domain in
  Array.iter (fun c -> Printf.printf "(%f, %f)\n" c.re c.im) time_domain