open System
open System.Diagnostics

type complex = C of float*float

let check (n: int) = true

let sum (a: complex) (b: complex) =
    match a, b with
        | C(x1, y1), C(x2, y2) -> C(x1+x2, y1+y2)

let mult (a: complex) (b: complex) =
    match a, b with
        | C(x1, y1), C(x2, y2) -> C(x1*x2-y1*y2, x1*y2+x2*y1)

let exp (e: float) =
    C(cos e, -sin e)

let opp (c: complex) =
    match c with
        | C(a, b) -> C(-a, -b)

let rec transform (x: complex array) =
    if not (check x.Length) then failwith "Error, input size invalid"

    if x.Length = 1 then x
    else
        let even = Array.init (x.Length/2) (fun i -> x.[2*i])
        let odd = Array.init (x.Length/2) (fun i -> x.[2*i+1])
        let es: complex array = transform even
        let os: complex array = transform odd
        let ret: complex array = Array.zeroCreate x.Length

        for i in 0..(x.Length/2)-1 do
            let e = 2. * Math.PI * float i / float x.Length
            ret.[i] <- sum (es.[i]) (mult (exp e) (os.[i]))
            ret.[i+(x.Length/2)] <- sum (es.[i]) (mult (opp (exp e)) (os.[i]))

        ret

let t = new Stopwatch()
t.Start()
let x = transform [|C(1., 0.); C(1., 0.); C(1., 0.); C(1., 0.) |]
printfn "tempo di esecuzione: %i" t.ElapsedMilliseconds
printfn "%A" x