trusted
69
edits
Fast Fourier transform: Difference between revisions
Jump to navigation
Jump to search
+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)
m (Applications category) |
(+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 31: | Line 31: | ||
done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | ||
</source> | </source> | ||
=== Simple recursive implementation === | |||
<source lang=apl> | |||
fft←{ | |||
1>K←2÷⍨M←≢⍵:⍵ | |||
0≠1|2⍟M:'Length of the input vector must be a power of 2' | |||
odd←∇(M⍴1 0)/⍵ | |||
even←∇(M⍴0 1)/⍵ | |||
exp←*(0J¯2×(○1)×(¯1+⍳K)÷M) | |||
(odd+T),odd-T←even×exp | |||
} | |||
</source> | |||
{{Works in|[[Dyalog APL]]}} | |||
Sample usage: | |||
fft 1 1 1 1 0 0 0 0 | |||
4 1J¯2.414213562 0 1J¯0.4142135624 0 1J0.4142135624 0 1J2.414213562 | |||
=== Dyalog APL === | === Dyalog APL === | ||
FFT appears in [[dfns.dws]], a [[workspace]] supplied with [[Dyalog APL]], in the context of fast multi-digit multiplication<ref>dfns.dws: [http://dfns.dyalog.com/n_xtimes.htm xtimes] — Fast multi-digit product using FFT</ref>. Extracted from there, it is there defined as: | FFT appears in [[dfns.dws]], a [[workspace]] supplied with [[Dyalog APL]], in the context of fast multi-digit multiplication<ref>dfns.dws: [http://dfns.dyalog.com/n_xtimes.htm xtimes] — Fast multi-digit product using FFT</ref>. Extracted from there, it is there defined as: | ||
| Line 39: | Line 57: | ||
FFT←{,(cube roots⍴⍵)floop cube ⍵} | FFT←{,(cube roots⍴⍵)floop cube ⍵} | ||
</source> | </source> | ||
== References == | == References == | ||
<references /> | <references /> | ||
[[Category:Applications]] | [[Category:Applications]] | ||