Fast Fourier transform: Difference between revisions
Content added Content deleted
No edit summary |
(Added a Scheme implementation.) |
||
Line 3,919: | Line 3,919: | ||
<pre>Vector(4.000 + 2.000i, 2.414 + 1.000i, -2.000, 2.414 + 1.828i, 2.000i, -0.414 + 1.000i, 2.000, -0.414 - 3.828i) |
<pre>Vector(4.000 + 2.000i, 2.414 + 1.000i, -2.000, 2.414 + 1.828i, 2.000i, -0.414 + 1.000i, 2.000, -0.414 - 3.828i) |
||
Vector(1.000, 1.000, 1.000, 1.000, 0.000, 2.000i, 0.000, 0.000)</pre> |
Vector(1.000, 1.000, 1.000, 1.000, 0.000, 2.000i, 0.000, 0.000)</pre> |
||
=={{header|Scheme}}== |
|||
{{works with|Chez Scheme}} |
|||
<lang scheme>; Compute and return the FFT of the given input vector using the Cooley-Tukey Radix-2 |
|||
; Decimation-in-Time (DIT) algorithm. The input is assumed to be a vector of complex |
|||
; numbers that is a power of two in length greater than zero. |
|||
(define fft-r2dit |
|||
(lambda (in-vec) |
|||
; The constant ( -2 * pi * i ). |
|||
(define -2*pi*i (* -2.0i (atan 0 -1))) |
|||
; The Cooley-Tukey Radix-2 Decimation-in-Time (DIT) procedure. |
|||
(define fft-r2dit-aux |
|||
(lambda (vec start leng stride) |
|||
(if (= leng 1) |
|||
(vector (vector-ref vec start)) |
|||
(let* ((leng/2 (truncate (/ leng 2))) |
|||
(evns (fft-r2dit-aux vec 0 leng/2 (* stride 2))) |
|||
(odds (fft-r2dit-aux vec stride leng/2 (* stride 2))) |
|||
(dft (make-vector leng))) |
|||
(do ((inx 0 (1+ inx))) |
|||
((>= inx leng/2) dft) |
|||
(let ((e (vector-ref evns inx)) |
|||
(o (* (vector-ref odds inx) (exp (* inx (/ -2*pi*i leng)))))) |
|||
(vector-set! dft inx (+ e o)) |
|||
(vector-set! dft (+ inx leng/2) (- e o)))))))) |
|||
; Call the Cooley-Tukey Radix-2 Decimation-in-Time (DIT) procedure w/ appropriate |
|||
; arguments as derived from the argument to the fft-r2dit procedure. |
|||
(fft-r2dit-aux in-vec 0 (vector-length in-vec) 1))) |
|||
; Test using a simple pulse. |
|||
(let* ((inp (vector 1.0 1.0 1.0 1.0 0.0 0.0 0.0 0.0)) |
|||
(dft (fft-r2dit inp))) |
|||
(printf "In: ~a~%" inp) |
|||
(printf "DFT: ~a~%" dft))</lang> |
|||
{{out}} |
|||
<pre> |
|||
In: #(1.0 1.0 1.0 1.0 0.0 0.0 0.0 0.0) |
|||
DFT: #(4.0 1.0-2.414213562373095i 0.0-0.0i 1.0-0.4142135623730949i 0.0 1.0+0.41421356237309515i 0.0+0.0i 0.9999999999999997+2.414213562373095i) |
|||
</pre> |
|||
=={{header|Scilab}}== |
=={{header|Scilab}}== |