\\ ---------------  GP code  ---------------------------------------
\\
\\ Time-stamp: <2002-12-08 14:25:12 cdoche>
\\
\\ Description: Routines for computing exact moments of Rudin-Shapiro polynomials 
\\ and the asymptotic behaviour of the moments of Rudin-Shapiro like polynomials such as Golay polynomials.
\\
\\
\\ Original author: Christophe Doche
\\			           cdoche@math.u-bordeaux.fr
\\        			  Université Bordeaux I
\\			           Laboratoire A2X	
\\
\\ Created:               Monday Aug 12 2002
\\ Last Modified:         Monday Jun 20 2005       
\\
\\======================================================================

/*
Let P_0 = 1, Q_0 = 1 and 
P_{n+1}=P_n+x^{2^n}Q_n
Q_{n+1}=P_n-x^{2^n}Q_n.
Then the P_n's are the so-called Rudin-Shapiro polynomials.
The exact moment of order q of P_n (the constant coefficient of (P_n(x)P_n(1/x))^{q/2}) 
is given for q even less than or equal to 32 and for arbitrary n by the procedure findmoment(q,n) */


read("data.gz");
read("data32.gz");

{goodrec(p,w)=
L=length(w):
v=Vec(p):
nb=0:
s0=0:lg=length(v):for(i=1,lg-1,s0=s0+eval(Str(u "" i ))*v[lg-i+1]):
for(j=0,L-lg,print(j):s=s0:for(i=1,lg-1,s=subst(s,eval(Str(u "" i )),w[i+j])):
if(w[lg+j]==-s,nb++,print(s," ",w[lg+j]))):if(nb==L-lg+1,print(p," ",goodpoly))}

{scalar(v1,v2)=
return(sum(i=1,length(v1),v1[i]*v2[i]))}

{nextone(w,val)=
local(lg):
lg=length(w):
return(concat(vector(lg-1,i,w[i+1]),val))}

{findmoment(l,q,n)=
local(lg,r,p,deg,mc,j,nv,lgmod):
deg=eval(Str("deg"""l"_"q)):
p=eval(Str("p"""l"_"q)):
m=eval(Str("m"""l"_"q)):
mc=eval(Str("M"""l))[q]:
r=eval(Str("r"""l"_"q)):
lg=mc[1]:
if(n<deg,return(m[n+1]),
if(lg>=n&lg-n<deg,return(mc=eval(Str("M"""l))[q][2][deg-lg+n])):
if(lg>n,mc=[deg-1,vector(deg,i,m[i])]):
lg=mc[1]:
j=n-lg:if(j>99,lgmod=floor((n-lg)/9),lgmod=0):
while(j>0,if(lgmod!=0&j%lgmod==0,print1("*")):
nv=lift(scalar(mc[2],r)):mc[2]=nextone(mc[2],nv):mc[1]++:
j--):if(lgmod!=0,print1("*")):eval(Str("M"""l"[""q""]="mc)):return(nv))}

addhelp(findmoment,"findmoment(l,q,n): Given l between 2 and 8, an even integer q and an integer n computes the exact moment of order q of the nth Rudin-Shapiro P_n");