> restart;
> with(linalg): with(plots,listplot,pointplot);
Warning, new definition for norm
Warning, new definition for trace

                        [listplot, pointplot]

> # Prozedur zur Berechnung des trigonometrischen Interpolationspolynoms f)
> # N Anzahl der Interpolationsknoten
> # r-1 Stellen zwischen den Interpolationsknoten werden ausgewertet
> # f Feld der Funktionswerte f(2 Pi k/N), k=0,...,N-1
> trigo:=proc(N,r,f)
> # option trace;
> global p;
> local dft,SandeTukey1,c,j,w,rho,e,d,q,l;
> SandeTukey1:=proc(a)
> # a Vektor von Zweierpotenzlaenge N=2^t
> # option trace;
> local N,m,m1,w,l,r,j,s,k,t,b,u,i,aa;
> N:=vectdim(a); b:=vector(N); aa:=vector(N); 
> for j from 1 to N do aa[j]:=a[j] od;
> t:=round(log[2](N)); m:=2*N;
> for i from t  by (-1) to 1 do
>   m:=m/2;  r:=round(N/m); w:=evalf(cos(2*Pi/m)-I*sin(2*Pi/m));
>   for j from 0 to r-1 do
>       for l from 0 to round(m/2)-1 do
>          s:=2*l*r; u:=round(s/2);
>          b[j+s+1]:=aa[j+u+1]+aa[j+u+round(N/2)+1];
>          b[j+s+r+1]:=(aa[j+u+1]-aa[j+u+round(N/2)+1])*w^l;
>       od
>   od;
>   for j from 1 to N do aa[j]:=b[j] od
> od;
> evalm(aa)
> end;
> p:=vector(r*N);
> c:=vector(N);
> c:=SandeTukey1(f);
> for j from 1 to N do c[j]:=c[j]/N od;
> for j from 0 to N-1 do p[r*j+1]:=f[j+1] od;
> w:=vector(r*N);
> for j from 0 to N*r-1 do w[j+1]:=evalf(cos(2*Pi*j/(r*N))+ I*sin(2*Pi*j/(r*N))) od;
> for rho from 1 to r-1 do
>     e:=vector(N); d:=vector(N); q:=vector(N);
>     for j from 0 to trunc(N/2) do
>         l:=(j*rho) mod (N*r);
>         e[j+1]:=w[l+1]
>     od;
>     for j from trunc(N/2)+1 to N-1 do
>         l:=(j-N)*rho mod (N*r);
>          e[j+1]:= w[l+1]
>     od;
>     for j from 0 to N-1 do d[j+1]:=c[j+1]*e[j+1] od;
>     q:=SandeTukey1(d);
>     for j from 1 to N-1 do d[j+1]:=q[N+1-j] od;
>     d[1]:=q[1];
>     for j from 0 to N-1 do p[j*r+rho+1]:=d[j+1] od
> od;
> listplot([seq([2*Pi*j/(r*N),Re(p[j+1])],j=0..r*N-1)]);
> end: 
> f:=vector(16,[-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8]);
> trigo(16,5,f);

     f := [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]


>