restart: N:=16: a:=10: Y:=array(0..N-1): for i from 0 to N-1 do Y[i]:=(1+a^2)/(1+a*i^2); od: W:=evalf(exp(-2*Pi*I/N)): for a2 from 0 to 1 do for a1 from 0 to 1 do for a0 from 0 to 1 do for b0 from 0 to 1 do add(Y[8*a3+4*a2+2*a1+a0]*W^(8*a3*b0),a3=0..1); X0[8*a2+4*a1+2*a0+b0]:=%; od: od: od: od: for a1 from 0 to 1 do for a0 from 0 to 1 do for b0 from 0 to 1 do for b1 from 0 to 1 do add(X0[8*a2+4*a1+2*a0+b0]*W^(4*a2*(2*b1+b0)),a2=0..1); X1[8*a1+4*a0+2*b0+b1]:=%; od: od: od: od: for a0 from 0 to 1 do for b0 from 0 to 1 do for b1 from 0 to 1 do for b2 from 0 to 1 do add(X1[8*a1+4*a0+2*b0+b1]*W^(2*a1*(4*b2+2*b1+b0)),a1=0..1); X2[8*a0+4*b0+2*b1+b2]:=%; od: od: od: od: for b3 from 0 to 1 do for b2 from 0 to 1 do for b1 from 0 to 1 do for b0 from 0 to 1 do add(X2[8*a0+4*b0+2*b1+b2]*W^(a0*(8*b3+4*b2+2*b1+b0)),a0=0..1); F[8*b3+4*b2+2*b1+b0]:=%; od: 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(Y[i])],i=0..N-1)]: plot(u,colour=green,thickness=2); LSUlUExPVEc2Jy0lJ0NVUlZFU0c2IzcyNyQkIiIhISIiJCIlNTUhIiI3JCQiIzUhIiIkIjA9PT09PT09KiEjOTckJCIjPyEiIiQiME1ZVGo5TVkjISM5NyQkIiNJISIiJCIwNiEqKTQsKik0NiEjOTckJCIjUyEiIiQiMCVlWUQ+SHRpISM6NyQkIiNdISIiJCIwN3FDUS9SLSUhIzo3JCQiI2chIiIkIjAsPU4kUnkoeiMhIzo3JCQiI3EhIiIkIjBUeWxaRXEwIyEjOjckJCIjISkhIiIkIjAxQGwtamNkIiEjOjckJCIjISohIiIkIjAjXCIqeWdQWDchIzo3JCQiJCsiISIiJCIwLCIqKjM1KiozNSEjOjckJCIkNSIhIiIkIi9pZilwOS1NKSEjOjckJCIkPyIhIiIkIjBKUUdeQCE0cSEjOzckJCIkSSIhIiIkIjAkSFdocnpzZiEjOzckJCIkUyIhIiIkIjBDP0JYTC86JiEjOzckJCIkXSIhIiIkIjBvZ01yJSpvWyUhIzstJStBWEVTTEFCRUxTRzYkUSE2IlEhNiItJSZDT0xPUkc2JiUkUkdCRyQiIiEhIiIkIiM1ISIiJCIiISEiIi0lKlRISUNLTkVTU0c2IyIiIy0lJVJPT1RHNictJSlCT1VORFNfWEc2IyQiJHElISIiLSUpQk9VTkRTX1lHNiMkIiMhKSEiIi0lLUJPVU5EU19XSURUSEc2IyQiJT9NISIiLSUuQk9VTkRTX0hFSUdIVEc2IyQiJStOISIiLSUpQ0hJTERSRU5HNiI= fu:=[seq([i,abs(F[i])],i=0..N-1)]: plot(fu,colour=green,thickness=2); LSUlUExPVEc2Jy0lJ0NVUlZFU0c2IzcyNyQkIiIhISIiJCIrLSNIJ2Y2ISIoNyQkIiM1ISIiJCIqVlwxNiIhIic3JCQiIz8hIiIkIisjcDtXMSIhIig3JCQiI0khIiIkIitLdERENSEiKDckJCIjUyEiIiQiK0U2KjMkKiohIik3JCQiI10hIiIkIitqVVJ6JyohIik3JCQiI2chIiIkIitXYicpKVwqISIpNyQkIiNxISIiJCIqdlIsUiohIig3JCQiIyEpISIiJCIrOlcjUU4qISIpNyQkIiMhKiEiIiQiK18oUixSKiEiKTckJCIkKyIhIiIkIitYYicpKVwqISIpNyQkIiQ1IiEiIiQiK2tVUnonKiEiKTckJCIkPyIhIiIkIitGNiozJCoqISIpNyQkIiRJIiEiIiQiK0t0REQ1ISIoNyQkIiRTIiEiIiQiKyNwO1cxIiEiKDckJCIkXSIhIiIkIipWXDE2IiEiJy0lK0FYRVNMQUJFTFNHNiRRITYiUSE2Ii0lJkNPTE9SRzYmJSRSR0JHJCIiISEiIiQiIzUhIiIkIiIhISIiLSUqVEhJQ0tORVNTRzYjIiIjLSUlUk9PVEc2Jy0lKUJPVU5EU19YRzYjJCIkcSUhIiItJSlCT1VORFNfWUc2IyQiI3EhIiItJS1CT1VORFNfV0lEVEhHNiMkIiU/TSEiIi0lLkJPVU5EU19IRUlHSFRHNiMkIiU1TiEiIi0lKUNISUxEUkVORzYi iu:=[seq([i,abs(invFFT[i])],i=0..N-1)]: plot(iu,colour=green,thickness=2); LSUlUExPVEc2Jy0lJ0NVUlZFU0c2IzcyNyQkIiIhISIiJCIrKioqKioqNDUhIig3JCQiIzUhIiIkIitEIz09PSohIio3JCQiIz8hIiIkIityWVRqQyEiKjckJCIjSSEiIiQiK14sKik0NiEiKjckJCIjUyEiIiQiKylHI0h0aSEjNTckJCIjXSEiIiQiK1FZIVItJSEjNTckJCIjZyEiIiQiK2NVeSh6IyEjNTckJCIjcSEiIiQiK2luLWQ/ISM1NyQkIiMhKSEiIiQiKzdMbXY6ISM1NyQkIiMhKiEiIiQiKyk9d2BDIiEjNTckJCIkKyIhIiIkIis3NCoqMzUhIzU3JCQiJDUiISIiJCIpOkBTJCkhIio3JCQiJD8iISIiJCIrV1osNHEhIzY3JCQiJEkiISIiJCIrKW8neXNmISM2NyQkIiRTIiEiIiQiK0RPVF1eISM2NyQkIiRdIiEiIiQiK1FmJW9bJSEjNi0lK0FYRVNMQUJFTFNHNiRRITYiUSE2Ii0lJkNPTE9SRzYmJSRSR0JHJCIiISEiIiQiIzUhIiIkIiIhISIiLSUqVEhJQ0tORVNTRzYjIiIjLSUlUk9PVEc2Jy0lKUJPVU5EU19YRzYjJCIkcSUhIiItJSlCT1VORFNfWUc2IyQiIyEpISIiLSUtQk9VTkRTX1dJRFRIRzYjJCIlP00hIiItJS5CT1VORFNfSEVJR0hURzYjJCIlK04hIiItJSlDSElMRFJFTkc2Ig== plot([u,iu],colour=[green,blue],thickness=[4,1]); LSUlUExPVEc2Ji0lJ0NVUlZFU0c2JTcyNyQkIiIhISIiJCIlNTUhIiI3JCQiIzUhIiIkIjA9PT09PT09KiEjOTckJCIjPyEiIiQiME1ZVGo5TVkjISM5NyQkIiNJISIiJCIwNiEqKTQsKik0NiEjOTckJCIjUyEiIiQiMCVlWUQ+SHRpISM6NyQkIiNdISIiJCIwN3FDUS9SLSUhIzo3JCQiI2chIiIkIjAsPU4kUnkoeiMhIzo3JCQiI3EhIiIkIjBUeWxaRXEwIyEjOjckJCIjISkhIiIkIjAxQGwtamNkIiEjOjckJCIjISohIiIkIjAjXCIqeWdQWDchIzo3JCQiJCsiISIiJCIwLCIqKjM1KiozNSEjOjckJCIkNSIhIiIkIi9pZilwOS1NKSEjOjckJCIkPyIhIiIkIjBKUUdeQCE0cSEjOzckJCIkSSIhIiIkIjAkSFdocnpzZiEjOzckJCIkUyIhIiIkIjBDP0JYTC86JiEjOzckJCIkXSIhIiIkIjBvZ01yJSpvWyUhIzstJSZDT0xPUkc2JiUkUkdCRyQiIiEhIiIkIiM1ISIiJCIiISEiIi0lKlRISUNLTkVTU0c2IyIiJS0lJ0NVUlZFU0c2JTcyNyQkIiIhISIiJCIrKioqKioqNDUhIig3JCQiIzUhIiIkIitEIz09PSohIio3JCQiIz8hIiIkIityWVRqQyEiKjckJCIjSSEiIiQiK14sKik0NiEiKjckJCIjUyEiIiQiKylHI0h0aSEjNTckJCIjXSEiIiQiK1FZIVItJSEjNTckJCIjZyEiIiQiK2NVeSh6IyEjNTckJCIjcSEiIiQiK2luLWQ/ISM1NyQkIiMhKSEiIiQiKzdMbXY6ISM1NyQkIiMhKiEiIiQiKyk9d2BDIiEjNTckJCIkKyIhIiIkIis3NCoqMzUhIzU3JCQiJDUiISIiJCIpOkBTJCkhIio3JCQiJD8iISIiJCIrV1osNHEhIzY3JCQiJEkiISIiJCIrKW8neXNmISM2NyQkIiRTIiEiIiQiK0RPVF1eISM2NyQkIiRdIiEiIiQiK1FmJW9bJSEjNi0lJkNPTE9SRzYmJSRSR0JHJCIiISEiIiQiIiEhIiIkIiM1ISIiLSUqVEhJQ0tORVNTRzYjIiIiLSUrQVhFU0xBQkVMU0c2JFEhNiJRITYiLSUlUk9PVEc2Jy0lKUJPVU5EU19YRzYjJCIkcSUhIiItJSlCT1VORFNfWUc2IyQiIyEpISIiLSUtQk9VTkRTX1dJRFRIRzYjJCIlP00hIiItJS5CT1VORFNfSEVJR0hURzYjJCIlK04hIiItJSlDSElMRFJFTkc2Ig== LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=