



restart:  

timing:=NULL:   #timings for generating the permutation
timing2:=NULL:  #timings for sorting the final permatution
memory:=NULL:   #keep trace of the amount of memory used

nmax_max:=1000;
step:=100;

for nmax from 100 to nmax_max by step do  

    st:=time(): 
    p:=4:   a[0,0]:=1.:           U[0]:=0:  s[0] := rand()/10^(12):         
    for n from 1 to nmax-1 do U[n]:=rand(0 .. 1)(): od: #print([seq(U[n],n=1..nmax-1)]);

    for n from 1 to nmax do   a[n,0]:=0.:
    	if U[nmax-n]=0 then for i  from 1 to n do a[n,i]:=a[n-1,i-1]/i: od:
	else for i  from 1 to n do a[n,i]:=-a[n-1,i-1]/i:a[n,0]:=a[n,0]-a[n,i]: od: fi: od:
            
    f := add(a[nmax, k]*x^k, k = 0..nmax): 
    t := s[0]*subs(x = 1., f): g :=-t+f:
    h :=add(a[nmax-1, k]*x^k, k = 0..nmax-1):
    if U[1]=0 then  c:=1.:  else  c:=0.: fi:  e:=0.5  :
    i:=0: while abs(c-e)>10^(-p) do i:=i+1: if i>100 then print("possible infinite loops", [seq(U[j],j=1..nmax)]) fi;
    e:=c: d:= c-(subs(x = c , g)/subs(x = c , h)): c:=d: od:  V[0] := c :
	               
    for n from 1 to nmax-2 do f:=h: 
       s[n]:=  (rand(0..10^(12))())/10.^(12): t:=s[n]*subs(x=c,f):
       g :=f-t:      h:=add(a[nmax-n-1, k]*x^k, k = 0..nmax-n-1):
       if U[n]=0 then  j :=h:  else  j :=-h: fi:  
       e:=0.5:	if U[n+1]=0 then  c:=1. else  c:=0. fi:
       i:=0: while abs(c-e)>10^(-p) do i:=i+1: if i>100 then print("possible infinite loops", [seq(s[j],j=1..nmax)]) fi;
       e:=c: d:= c-subs(x = c , g)/subs(x = c , j):   c:=d: od:  V[n]:=c :  od:

   f:=a[1,0]+a[1,1]*x: 
   s[nmax-1]:=rand(0..10^(12))()/10^(12):
   t:=s[nmax-1]*subs(x=c,f):  
   V[nmax-1]:=(t-a[1,0])/a[1,1]:

   L:=[seq(V[n],n=0..nmax-1)]:	   timing:=timing,(time()-st)*secondes;
   st:=time():

  LL:=[op(sort({op(L)}))]:
   for k from 1 to nops(LL) do L:=subs(LL[k]=k,L) od: L;
  timing2:=timing2,(time()-st)*seconde:
  memory:=memory,evalf(trunc(kernelopts(bytesalloc)/10^4)/100,4)*Mo:

print(nmax,[timing][nops([timing])],[memory][nops([memory])]);
od: #fin des différentes valeur de nmax
