restart:

N:=8:

f:=array(0..N-1):

for i from 0 to N-1 do f[i]:=i;

od:

W:=evalf(exp(-2*Pi*I/N)):

for a1 from 0 to 1 do

for a0 from 0 to 1 do

for b0 from 0 to 1 do

add(f[4*a2+2*a1+a0]*W^(4*a2*b0),a2=0..1);

X0[4*a1+2*a0+b0]:=%;

od: od: od:

for a0 from 0 to 1 do

for b0 from 0 to 1 do

for b1 from 0 to 1 do

add(X0[4*a1+2*a0+b0]*W^(2*a1*(2*b1+b0)),a1=0..1);

X1[4*a0+2*b0+b1]:=%;

od: od: od:

for b2 from 0 to 1 do

for b1 from 0 to 1 do

for b0 from 0 to 1 do

add(X1[4*a0+2*b0+b1]*W^(a0*(4*b2+2*b1+b0)),a0=0..1);

F[4*b2+2*b1+b0]:=%;

od: od: od:

for i from 0 to N-1 do

invFFT[i]:=(1/N)*sum(F[k]*W^(-i*k),k=0..N-1):

od:

u:=[seq([i,abs(f[i])],i=0..N-1)]:

plot(u,colour=green,thickness=2);

LSUlUExPVEc2Jy0lJ0NVUlZFU0c2IzcqNyQkIiIhISIiJCIiISEiIjckJCIjNSEiIiQiIzUhIiI3JCQiIz8hIiIkIiM/ISIiNyQkIiNJISIiJCIjSSEiIjckJCIjUyEiIiQiI1MhIiI3JCQiI10hIiIkIiNdISIiNyQkIiNnISIiJCIjZyEiIjckJCIjcSEiIiQiI3EhIiItJStBWEVTTEFCRUxTRzYkUSE2IlEhNiItJSZDT0xPUkc2JiUkUkdCRyQiIiEhIiIkIiM1ISIiJCIiISEiIi0lKlRISUNLTkVTU0c2IyIiIy0lJVJPT1RHNictJSlCT1VORFNfWEc2IyQiJFMkISIiLSUpQk9VTkRTX1lHNiMkIiQ/IiEiIi0lLUJPVU5EU19XSURUSEc2IyQiJSFlJCEiIi0lLkJPVU5EU19IRUlHSFRHNiMkIiVnTSEiIi0lKUNISUxEUkVORzYi

u:=[seq([i,abs(F[i])],i=0..N-1)]:

plot(u,colour=green,thickness=2);

LSUlUExPVEc2Jy0lJ0NVUlZFU0c2IzcqNyQkIiIhISIiJCIkIUchIiI3JCQiIzUhIiIkIipQXV8vIiEiKDckJCIjPyEiIiQiK01VJm9sJiEiKjckJCIjSSEiIiQiKnpvJkhWISIpNyQkIiNTISIiJCIqKSoqKioqKlIhIik3JCQiI10hIiIkIisiem8mSFYhIio3JCQiI2chIiIkIitKVSZvbCYhIio3JCQiI3EhIiIkIitwLkRYNSEiKS0lK0FYRVNMQUJFTFNHNiRRITYiUSE2Ii0lJkNPTE9SRzYmJSRSR0JHJCIiISEiIiQiIzUhIiIkIiIhISIiLSUqVEhJQ0tORVNTRzYjIiIjLSUlUk9PVEc2Jy0lKUJPVU5EU19YRzYjJCIkNSUhIiItJSlCT1VORFNfWUc2IyQiI3EhIiItJS1CT1VORFNfV0lEVEhHNiMkIiU1TiEiIi0lLkJPVU5EU19IRUlHSFRHNiMkIiU1TiEiIi0lKUNISUxEUkVORzYi

u:=[seq([i,abs(invFFT[i])],i=0..N-1)]:

plot(u,colour=green,thickness=2);

LSUlUExPVEc2Jy0lJ0NVUlZFU0c2IzcqNyQkIiIhISIiJCIrdHhHUXUhIz03JCQiIzUhIiIkIistKysrNSEiKjckJCIjPyEiIiQiKywrKys/ISIqNyQkIiNJISIiJCIjSSEiIjckJCIjUyEiIiQiKy8rKytTISIqNyQkIiNdISIiJCIrLysrK10hIio3JCQiI2chIiIkIis3KysrZyEiKjckJCIjcSEiIiQiKzYrKytxISIqLSUrQVhFU0xBQkVMU0c2JFEhNiJRITYiLSUmQ09MT1JHNiYlJFJHQkckIiIhISIiJCIjNSEiIiQiIiEhIiItJSpUSElDS05FU1NHNiMiIiMtJSVST09URzYnLSUpQk9VTkRTX1hHNiMkIiRTJCEiIi0lKUJPVU5EU19ZRzYjJCIkPyIhIiItJS1CT1VORFNfV0lEVEhHNiMkIiUhZSQhIiItJS5CT1VORFNfSEVJR0hURzYjJCIlZ00hIiItJSlDSElMRFJFTkc2Ig==