Fast Fourier transform: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 2,673: | Line 2,673: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<lang Phix>-- |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- |
|||
-- demo\rosetta\FastFourierTransform.exw |
|||
-- demo\rosetta\FastFourierTransform.exw |
|||
-- ===================================== |
|||
-- ===================================== |
|||
-- |
|||
-- |
|||
-- Originally written by Robert Craig and posted to EuForum Dec 13, 2001 |
|||
-- Originally written by Robert Craig and posted to EuForum Dec 13, 2001 |
|||
-- |
|||
--</span> |
|||
constant REAL = 1, IMAG = 2 |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">REAL</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">IMAG</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span> |
|||
type complex(sequence x) |
|||
<span style="color: #008080;">type</span> <span style="color: #004080;">complex</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
return length(x)=2 and atom(x[REAL]) and atom(x[IMAG]) |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">2</span> <span style="color: #008080;">and</span> <span style="color: #004080;">atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">REAL</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">and</span> <span style="color: #004080;">atom</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">IMAG</span><span style="color: #0000FF;">])</span> |
|||
end type |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">type</span> |
|||
function p2round(integer x) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">p2round</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
-- rounds x up to a power of two |
|||
<span style="color: #000080;font-style:italic;">-- rounds x up to a power of two</span> |
|||
integer p = 1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
while p<x do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><</span><span style="color: #000000;">x</span> <span style="color: #008080;">do</span> |
|||
p += p |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">p</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
return p |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">p</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function log2(atom x) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">log_2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
-- return log2 of x, or -1 if x is not a power of 2 |
|||
<span style="color: #000080;font-style:italic;">-- return log2 of x, or -1 if x is not a power of 2</span> |
|||
if x>0 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
integer p = -1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
while floor(x)=x do |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">x</span> <span style="color: #008080;">do</span> |
|||
x /= 2 |
|||
<span style="color: #000000;">x</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">2</span> |
|||
p += 1 |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
if x=0.5 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0.5</span> <span style="color: #008080;">then</span> |
|||
return p |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">p</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return -1 |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function bitrev(sequence a) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">bitrev</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
-- bitrev an array of complex numbers |
|||
<span style="color: #000080;font-style:italic;">-- bitrev an array of complex numbers</span> |
|||
integer j=1, n = length(a) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to n-1 do |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
if i<j then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
{a[i],a[j]} = {a[j],a[i]} |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">j</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]}</span> |
|||
integer k = n/2 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
while k<j do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span> |
|||
j -= k |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><</span><span style="color: #000000;">j</span> <span style="color: #008080;">do</span> |
|||
k /= 2 |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">k</span> |
|||
end while |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">2</span> |
|||
j = j+k |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end for |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">k</span> |
|||
return a |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function cmult(complex arg1, complex arg2) |
|||
-- complex multiply |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">cmult</span><span style="color: #0000FF;">(</span><span style="color: #004080;">complex</span> <span style="color: #000000;">arg1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">complex</span> <span style="color: #000000;">arg2</span><span style="color: #0000FF;">)</span> |
|||
return {arg1[REAL]*arg2[REAL]-arg1[IMAG]*arg2[IMAG], |
|||
<span style="color: #000080;font-style:italic;">-- complex multiply </span> |
|||
arg1[REAL]*arg2[IMAG]+arg1[IMAG]*arg2[REAL]} |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">arg1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">REAL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">arg2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">REAL</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">arg1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">IMAG</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">arg2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">IMAG</span><span style="color: #0000FF;">],</span> |
|||
end function |
|||
<span style="color: #000000;">arg1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">REAL</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">arg2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">IMAG</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">arg1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">IMAG</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">arg2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">REAL</span><span style="color: #0000FF;">]}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function ip_fft(sequence a) |
|||
-- perform an in-place fft on an array of complex numbers |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">ip_fft</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
-- that has already been bit reversed |
|||
<span style="color: #000080;font-style:italic;">-- perform an in-place fft on an array of complex numbers |
|||
integer n = length(a) |
|||
-- that has already been bit reversed</span> |
|||
integer ip, le, le1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
complex u, w, t |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ip</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">le</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">le1</span> |
|||
<span style="color: #004080;">complex</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span> |
|||
for l=1 to log2(n) do |
|||
le = power(2, l) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">log_2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
le1 = le/2 |
|||
<span style="color: #000000;">le</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> |
|||
u = {1, 0} |
|||
<span style="color: #000000;">le1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">le</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span> |
|||
w = {cos(PI/le1), sin(PI/le1)} |
|||
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> |
|||
for j=1 to le1 do |
|||
<span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">cos</span><span style="color: #0000FF;">(</span><span style="color: #004600;">PI</span><span style="color: #0000FF;">/</span><span style="color: #000000;">le1</span><span style="color: #0000FF;">),</span> <span style="color: #7060A8;">sin</span><span style="color: #0000FF;">(</span><span style="color: #004600;">PI</span><span style="color: #0000FF;">/</span><span style="color: #000000;">le1</span><span style="color: #0000FF;">)}</span> |
|||
for i=j to n by le do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">le1</span> <span style="color: #008080;">do</span> |
|||
ip = i+le1 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">j</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">by</span> <span style="color: #000000;">le</span> <span style="color: #008080;">do</span> |
|||
t = cmult(a[ip], u) |
|||
<span style="color: #000000;">ip</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">le1</span> |
|||
a[ip] = sq_sub(a[i],t) |
|||
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cmult</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ip</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">)</span> |
|||
a[i] = sq_add(a[i],t) |
|||
<span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ip</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
|||
u = cmult(u, w) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cmult</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return a |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function fft(sequence a) |
|||
integer n = length(a) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">fft</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
if log2(n)=-1 then |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
puts(1, "input vector length is not a power of two, padded with 0's\n\n") |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">log_2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
n = p2round(n) |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"input vector length is not a power of two, padded with 0's\n\n"</span><span style="color: #0000FF;">)</span> |
|||
-- pad with 0's |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p2round</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
for j=length(a)+1 to n do |
|||
<span style="color: #000080;font-style:italic;">-- pad with 0's </span> |
|||
a = append(a,{0, 0}) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">})</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
a = ip_fft(bitrev(a)) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
-- reverse output from fft to switch +ve and -ve frequencies |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ip_fft</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bitrev</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">))</span> |
|||
for i=2 to n/2 do |
|||
<span style="color: #000080;font-style:italic;">-- reverse output from fft to switch +ve and -ve frequencies</span> |
|||
integer j = n+2-i |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
{a[i],a[j]} = {a[j],a[i]} |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span> |
|||
end for |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]}</span> |
|||
return a |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function ifft(sequence a) |
|||
integer n = length(a) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">ifft</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
if log2(n)=-1 then ?9/0 end if -- (or as above?) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
a = ip_fft(bitrev(a)) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">log_2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (or as above?)</span> |
|||
-- modifies results to get inverse fft |
|||
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ip_fft</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bitrev</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">))</span> |
|||
for i=1 to n do |
|||
<span style="color: #000080;font-style:italic;">-- modifies results to get inverse fft</span> |
|||
a[i] = sq_div(a[i],n) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
return a |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
constant a = {{1, 0}, |
|||
{1, 0}, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{1, 0}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{1, 0}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{0, 0}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{0, 0}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{0, 0}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{0, 0}} |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}}</span> |
|||
printf(1, "Results of %d-point fft:\n\n", length(a)) |
|||
ppOpt({pp_Nest,1,pp_IntFmt,"%10.6f",pp_FltFmt,"%10.6f"}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Results of %d-point fft:\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">))</span> |
|||
pp(fft(a)) |
|||
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%10.6f"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_FltFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%10.6f"</span><span style="color: #0000FF;">})</span> |
|||
printf(1, "\nResults of %d-point inverse fft (rounded to 6 d.p.):\n\n", length(a)) |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fft</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">))</span> |
|||
pp(ifft(fft(a)))</lang> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"\nResults of %d-point inverse fft (rounded to 6 d.p.):\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ifft</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fft</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)))</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |