open System
open System.Numerics

module FastFourierTransform =
    let tau = 2. * Math.PI

    let root a inv = 
        if not inv then Complex.FromPolarCoordinates(1., a)
        else Complex.FromPolarCoordinates(1., a) |> Complex.Conjugate

    let fft x invert =
        let rec inner x invert =
            match x, invert with
            | [||], _ -> [||]
            | [|x|], _ -> [|x|]
            | x, invert ->
                x
                |> Array.mapi (fun i c -> i % 2 = 0, c)
                |> Array.partition fst
                |> fun (even, odd) -> inner (Array.map snd even) invert, inner (Array.map snd odd) invert
                ||> Array.mapi2 (fun i even odd ->
                    let btf = odd * (root (tau * (float i / float x.Length)) invert)
                    even + btf, even - btf)
                |> Array.unzip
                ||> Array.append

        inner x invert
        |> function
            | list ->
                if invert then list |> Array.map (fun i -> i / Complex(float x.Length, 0.))
                else list



고속푸리에변환이 먼가요