Fast Fourier transform: Difference between revisions
m (→{{header|J}}) |
(→{{header|Perl 6}}: Add Python) |
||
Line 42: | Line 42: | ||
wave: 0.000 0.924 0.707 -0.383 -1.000 -0.383 0.707 0.924 0.000 -0.924 -0.707 0.383 1.000 0.383 -0.707 -0.924 |
wave: 0.000 0.924 0.707 -0.383 -1.000 -0.383 0.707 0.924 0.000 -0.924 -0.707 0.383 1.000 0.383 -0.707 -0.924 |
||
fft: 0.000 0.000 0.000 8.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 8.000 0.000 0.000 |
fft: 0.000 0.000 0.000 8.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 8.000 0.000 0.000 |
||
=={{header|Python}}== |
|||
Using module [http://numpy.scipy.org/ numpy]. |
|||
<lang python>>>> from numpy.fft import fft |
|||
>>> from numpy import array |
|||
>>> a = array((0.0, 0.924, 0.707, -0.383, -1.0, -0.383, 0.707, 0.924, 0.0, -0.924, -0.707, 0.383, 1.0, 0.383, -0.707, -0.924)) |
|||
>>> fft(a) |
|||
array([ 0.00000000e+00 +0.00000000e+00j, |
|||
-7.77156117e-16 +1.28750059e-03j, |
|||
0.00000000e+00 +0.00000000e+00j, |
|||
-7.66053887e-15 -8.00062775e+00j, |
|||
0.00000000e+00 +0.00000000e+00j, |
|||
-8.88178420e-16 -1.23179335e-03j, |
|||
0.00000000e+00 +0.00000000e+00j, |
|||
2.33146835e-15 +6.83454981e-04j, |
|||
0.00000000e+00 +0.00000000e+00j, |
|||
-7.77156117e-16 -6.83454981e-04j, |
|||
0.00000000e+00 +0.00000000e+00j, |
|||
2.99760217e-15 +1.23179335e-03j, |
|||
0.00000000e+00 +0.00000000e+00j, |
|||
2.44249065e-15 +8.00062775e+00j, |
|||
0.00000000e+00 +0.00000000e+00j, 2.33146835e-15 -1.28750059e-03j])</lang> |
Revision as of 18:51, 8 February 2011
The purpose of this task is to calculate the FFT (Fast Fourier Transform) of an input sequence. The most general case allows for complex numbers at the input and results in a sequence of equal length, again of complex numbers. If you need to restrict yourself to real numbers the output should be the magnitude (i.e. sqrt(re²+im²)) of the complex result. The classic version is the recursive Cooley–Tukey FFT. Wikipedia has pseudocode for that. Further optimizations are possible but not required.
J
Based on j:Essays/FFT, with some simplifications, sacrificing accuracy, optimizations and convenience not visible here, for clarity:
<lang j>cube =: ($~ q:@#) :. , rou =: ^@j.@o.@(% #)@i.@-: NB. roots of unity floop =: 4 : 'for_r. i.#$x do. (y=.{."1 y) ] x=.(+/x) ,&,:"r (-/x)*y end.' fft =: ] floop&.cube rou@#</lang>
Example:
<lang j> require'printf'
fmt =: [:, sprintf~&'%7.3f'"0 ('wave:',:'fft:'),.fmt"1 (,: |@fft) 1 o. 2p1*3r16 * i.16
wave: 0.000 0.924 0.707 -0.383 -1.000 -0.383 0.707 0.924 0.000 -0.924 -0.707 0.383 1.000 0.383 -0.707 -0.924 fft: 0.000 0.000 0.000 8.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 8.000 0.000 0.000</lang>
Note that sprintf does not support complex arguments, so we only display the magnitude of the fft here.
Perl 6
<lang perl6>sub fft {
return @_ if @_ == 1; my @evn = fft( @_[0,2...^* >= @_] ); my @odd = fft( @_[1,3...^* >= @_] ); my $twd = 2i * pi / @_; # twiddle factor @odd »*=« (^@odd).map(* * $twd)».exp; return @evn »+« @odd, @evn »-« @odd;
}
my @seq = ^16; my $cycles = 3; my @wave = (@seq »*» (2*pi / @seq * $cycles))».sin; say "wave: ", @wave.fmt("%7.3f");
say "fft: ", fft(@wave)».abs.fmt("%7.3f");</lang>
Output:
wave: 0.000 0.924 0.707 -0.383 -1.000 -0.383 0.707 0.924 0.000 -0.924 -0.707 0.383 1.000 0.383 -0.707 -0.924 fft: 0.000 0.000 0.000 8.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 8.000 0.000 0.000
Python
Using module numpy. <lang python>>>> from numpy.fft import fft >>> from numpy import array >>> a = array((0.0, 0.924, 0.707, -0.383, -1.0, -0.383, 0.707, 0.924, 0.0, -0.924, -0.707, 0.383, 1.0, 0.383, -0.707, -0.924)) >>> fft(a) array([ 0.00000000e+00 +0.00000000e+00j,
-7.77156117e-16 +1.28750059e-03j, 0.00000000e+00 +0.00000000e+00j, -7.66053887e-15 -8.00062775e+00j, 0.00000000e+00 +0.00000000e+00j, -8.88178420e-16 -1.23179335e-03j, 0.00000000e+00 +0.00000000e+00j, 2.33146835e-15 +6.83454981e-04j, 0.00000000e+00 +0.00000000e+00j, -7.77156117e-16 -6.83454981e-04j, 0.00000000e+00 +0.00000000e+00j, 2.99760217e-15 +1.23179335e-03j, 0.00000000e+00 +0.00000000e+00j, 2.44249065e-15 +8.00062775e+00j, 0.00000000e+00 +0.00000000e+00j, 2.33146835e-15 -1.28750059e-03j])</lang>