 IN: math.transforms.fft
 
 <PRIVATE
+
+DEFER: (fft)
 
 ! Discrete Fourier Transform
 :: (slow-fft) ( seq inverse? -- seq' )

        2bi append
    ] if ; inline recursive

PRIVATE>

ERROR: not-enough-data ;

: fft ( seq -- seq' )
    [ not-enough-data ] [
        f over length even? [ (fft) ] [ (slow-fft) ] if
    ] if-empty ;

: ifft ( seq -- seq' )
    [ not-enough-data ] [
        t over length even? [ (fft) ] [ (slow-fft) ] if
    ] if-empty ;

: correlate ( x y -- z )
    [ fft ] [ reverse fft ] bi* v* ifft ;

    ] map ; inline

! Cooley–Tukey Algorithm
:: (fast-fft) ( seq inverse? -- seq' )
    seq length :> N
    N 1 = [ seq ] [
        seq even-indices inverse? (fft)
