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 rndGen = new System.Random(int System.DateTime.Now.Ticks)
let a: complex array = Array.init 65536 (fun _ ->
    let x, y = float rndGen.next(128), float rndGen.next(128)
    C(x, y)
)
let t = new Stopwatch()
t.Start()
//let x = transform [|C(1., 0.); C(1., 0.); C(1., 0.); C(1., 0.) |]
let x = transform a
printfn "tempo di esecuzione: %i" t.ElapsedMilliseconds
printfn "%A" x

b3BlbiBTeXN0ZW0Kb3BlbiBTeXN0ZW0uRGlhZ25vc3RpY3MKCnR5cGUgY29tcGxleCA9IEMgb2YgZmxvYXQqZmxvYXQKCmxldCBjaGVjayAobjogaW50KSA9IHRydWUKCmxldCBzdW0gKGE6IGNvbXBsZXgpIChiOiBjb21wbGV4KSA9CiAgICBtYXRjaCBhLCBiIHdpdGgKICAgICAgICB8IEMoeDEsIHkxKSwgQyh4MiwgeTIpIC0+IEMoeDEreDIsIHkxK3kyKQoKbGV0IG11bHQgKGE6IGNvbXBsZXgpIChiOiBjb21wbGV4KSA9CiAgICBtYXRjaCBhLCBiIHdpdGgKICAgICAgICB8IEMoeDEsIHkxKSwgQyh4MiwgeTIpIC0+IEMoeDEqeDIteTEqeTIsIHgxKnkyK3gyKnkxKQogICAgCmxldCBleHAgKGU6IGZsb2F0KSA9CiAgICBDKGNvcyBlLCAtc2luIGUpCgpsZXQgb3BwIChjOiBjb21wbGV4KSA9CiAgICBtYXRjaCBjIHdpdGgKICAgICAgICB8IEMoYSwgYikgLT4gQygtYSwgLWIpCgpsZXQgcmVjIHRyYW5zZm9ybSAoeDogY29tcGxleCBhcnJheSkgPQogICAgaWYgbm90IChjaGVjayB4Lkxlbmd0aCkgdGhlbiBmYWlsd2l0aCAiRXJyb3IsIGlucHV0IHNpemUgaW52YWxpZCIKICAgIAogICAgaWYgeC5MZW5ndGggPSAxIHRoZW4geAogICAgZWxzZQogICAgICAgIGxldCBldmVuID0gQXJyYXkuaW5pdCAoeC5MZW5ndGgvMikgKGZ1biBpIC0+IHguWzIqaV0pCiAgICAgICAgbGV0IG9kZCA9IEFycmF5LmluaXQgKHguTGVuZ3RoLzIpIChmdW4gaSAtPiB4LlsyKmkrMV0pCiAgICAgICAgbGV0IGVzOiBjb21wbGV4IGFycmF5ID0gdHJhbnNmb3JtIGV2ZW4KICAgICAgICBsZXQgb3M6IGNvbXBsZXggYXJyYXkgPSB0cmFuc2Zvcm0gb2RkCiAgICAgICAgbGV0IHJldDogY29tcGxleCBhcnJheSA9IEFycmF5Lnplcm9DcmVhdGUgeC5MZW5ndGgKICAgICAgICAKICAgICAgICBmb3IgaSBpbiAwLi4oeC5MZW5ndGgvMiktMSBkbwogICAgICAgICAgICBsZXQgZSA9IDIuICogTWF0aC5QSSAqIGZsb2F0IGkgLyBmbG9hdCB4Lkxlbmd0aAogICAgICAgICAgICByZXQuW2ldIDwtIHN1bSAoZXMuW2ldKSAobXVsdCAoZXhwIGUpIChvcy5baV0pKQogICAgICAgICAgICByZXQuW2krKHguTGVuZ3RoLzIpXSA8LSBzdW0gKGVzLltpXSkgKG11bHQgKG9wcCAoZXhwIGUpKSAob3MuW2ldKSkKCiAgICAgICAgcmV0CgpsZXQgcm5kR2VuID0gbmV3IFN5c3RlbS5SYW5kb20oaW50IFN5c3RlbS5EYXRlVGltZS5Ob3cuVGlja3MpCmxldCBhOiBjb21wbGV4IGFycmF5ID0gQXJyYXkuaW5pdCA2NTUzNiAoZnVuIF8gLT4KICAgIGxldCB4LCB5ID0gZmxvYXQgcm5kR2VuLm5leHQoMTI4KSwgZmxvYXQgcm5kR2VuLm5leHQoMTI4KQogICAgQyh4LCB5KQopCmxldCB0ID0gbmV3IFN0b3B3YXRjaCgpCnQuU3RhcnQoKQovL2xldCB4ID0gdHJhbnNmb3JtIFt8QygxLiwgMC4pOyBDKDEuLCAwLik7IEMoMS4sIDAuKTsgQygxLiwgMC4pIHxdCmxldCB4ID0gdHJhbnNmb3JtIGEKcHJpbnRmbiAidGVtcG8gZGkgZXNlY3V6aW9uZTogJWkiIHQuRWxhcHNlZE1pbGxpc2Vjb25kcwpwcmludGZuICIlQSIgeA==