Anonymous user
Fast Fourier transform: Difference between revisions
→{{header|Python}}
Line 915:
0.000000000000+0.000000000000I
0.999999999999+2.414213562373I</pre>
=={{header|Prolog}}==
<lang prolog>:- dynamic twiddles/2.
%_______________________________________________________________
% Arithemetic for complex numbers and lists of complex numbers
add(cx(R1,I1),cx(R2,I2),cx(R,I)) :- R is R1+R2, I is I1+I2.
sub(cx(R1,I1),cx(R2,I2),cx(R,I)) :- R is R1-R2, I is I1-I2.
mul(cx(R1,I1),cx(R2,I2),cx(R,I)) :- R is R1*R2-I1*I2, I is R1*I2+R2*I1.
polar_cx(Mag, Theta, cx(R, I)) :- % Euler
R is Mag * cos(Theta), I is Mag * sin(Theta).
%___________________________________________________
% FFT Implementation
tw(0,cx(1,0)) :- !. % Calculate e^(-2*pi*k/N)
tw(Tf, Cx) :- twiddles(Tf, Cx), !. % dynamic?
tw(Tf, Cx) :- polar_cx(1.0, -2*pi*Tf, Cx), assert(twiddles(Tf, Cx)).
fftVals(N, Even, Odd, V0, V1) :- % solves all V0,V1 for N,Even,Odd
nth0(K,Even,E), nth0(K,Odd,O), Tf is K rdiv N, tw(Tf,Cx),
mul(Cx,O,M), add(E,M,V0), sub(E,M,V1).
split([],[],[]). % split [[a0,b0],[a1,b1],...] into [a0,a1,...] and [b0,b1,...]
split([[V0,V1]|T], [V0|T0], [V1|T1]) :- !, split(T, T0, T1).
fft([H], [H]).
fft([H|T], List) :-
length([H|T],N),
findall(Ve, (nth0(I,[H|T],Ve),I mod 2 =:= 0), EL), !, fft(EL, Even),
findall(Vo, (nth0(I,T,Vo),I mod 2 =:= 0),OL), !, fft(OL, Odd),
findall([V0,V1],fftVals(N,Even,Odd,V0,V1),FFTVals), % calc FFT
split(FFTVals,L0,L1), append(L0,L1,List).
%___________________________________________________
test :- D=[cx(1,0),cx(1,0),cx(1,0),cx(1,0),cx(0,0),cx(0,0),cx(0,0),cx(0,0)],
time(fft(D,DRes)), writef('fft=%w', [DRes]).</lang>
'''Output:'''
<pre>test.
% 681 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
fft=[cx(4,0),cx(1.0,-2.414213562373095),cx(0.0,0.0),cx(1.0,-0.4142135623730949),cx(0,0),cx(0.9999999999999999,0.4142135623730949),cx(0.0,0.0),cx(0.9999999999999997,2.414213562373095)]
</pre>
=={{header|Python}}==
| |||