17 lines
534 B
Common Lisp
17 lines
534 B
Common Lisp
(define -∏*2 (complex 0 (* -2 PI)))
|
|
|
|
(define (fft xs N)
|
|
(if (<= N 1) xs
|
|
(let* [
|
|
(N/2 (/ N 2))
|
|
(even (fft (for/vector ([i (in-range 0 N 2)]) [xs i]) N/2))
|
|
(odd (fft (for/vector ([i (in-range 1 N 2)]) [xs i]) N/2))
|
|
]
|
|
(for ((k N/2)) (vector*= odd k (exp (/ (* -∏*2 k) N ))))
|
|
(vector-append (vector-map + even odd) (vector-map - even odd)))))
|
|
|
|
(define data #( 1 1 1 1 0 0 0 0 ))
|
|
|
|
(fft data 8)
|
|
→ #( 4+0i 1-2.414213562373095i 0+0i 1-0.4142135623730949i
|
|
0+0i 1+0.4142135623730949i 0+0i 1+2.414213562373095i)
|