trusted
69
edits
Fast Fourier transform: Difference between revisions
Jump to navigation
Jump to search
→Simple recursive implementation
(+a working modern version; shortened from RosettaCode, but also verified according to "Digital Image Processing" by Gonzalez and Wood (4th edition, eqns. 4-167, 4-168)) |
|||
| Line 42: | Line 42: | ||
(odd+T),odd-T←even×exp | (odd+T),odd-T←even×exp | ||
} | } | ||
ifft←{(≢⍵)÷⍨+fft(+⍵)} | |||
test←{⎕←'Error: ',⍕⌈/(10○⊢)(⍵-ifft fft ⍵)} | |||
</source> | </source> | ||
{{Works in|[[Dyalog APL]]}} | {{Works in|[[Dyalog APL]]}} | ||
| Line 48: | Line 50: | ||
fft 1 1 1 1 0 0 0 0 | fft 1 1 1 1 0 0 0 0 | ||
4 1J¯2.414213562 0 1J¯0.4142135624 0 1J0.4142135624 0 1J2.414213562 | 4 1J¯2.414213562 0 1J¯0.4142135624 0 1J0.4142135624 0 1J2.414213562 | ||
Inverse FFT can be defined for testing: | |||
<source lang=apl> | |||
ifft←{(≢⍵)÷⍨+fft(+⍵)} | |||
test←{⌈/(10○⊢)(⍵-ifft fft ⍵)} | |||
test 1 1 1 1 0 0 0 0 | |||
7.850462E¯17 | |||
</source> | |||
=== Dyalog APL === | === Dyalog APL === | ||