16 lines
907 B
Common Lisp
16 lines
907 B
Common Lisp
;;; This is adapted from the Python sample; it uses lists for simplicity.
|
|
;;; Production code would use complex arrays (for compiler optimization).
|
|
;;; This version exhibits LOOP features, closing with compositional golf.
|
|
(defun fft (x &aux (length (length x)))
|
|
;; base case: return the list as-is
|
|
(if (<= length 1) x
|
|
;; collect alternating elements into separate lists...
|
|
(loop for (a b) on x by #'cddr collect a into as collect b into bs finally
|
|
;; ... and take the FFT of both;
|
|
(let* ((ffta (fft as)) (fftb (fft bs))
|
|
;; incrementally phase shift each element of the 2nd list
|
|
(aux (loop for b in fftb and k from 0 by (/ pi length -1/2)
|
|
collect (* b (cis k)))))
|
|
;; finally, concatenate the sum and difference of the lists
|
|
(return (mapcan #'mapcar '(+ -) `(,ffta ,ffta) `(,aux ,aux)))))))
|