// This is just an example of how using the GT
// to evaluate a polynomial is faster than using
// sums and prods

p:=11; // char.
k:=10; // exponent of the field
n:=4; // (lenght - 1) of Witt vectors

maxdeg:=20;  // max. degree of x and y

print "p, k, n, maxdeg = ", p, k, n, maxdeg;

F<a>:=GF(p^k);
P<x0,x1,x2,x3,y0,y1,y2,y3>:=PolynomialRing(F,8);

// f is the polynomial
f:=[ ];

for i in [0..maxdeg] do
    for j in [0..maxdeg] do
        Append(~f,[* [ Random(F) : l in [0..n] ], i, j *]);
    end for;
end for; 

// will eval f at (x,y)
x:= [ Random(F) : l in [0..n] ];
y:= [ Random(F) : l in [0..n] ];

// x:=[ &+[ Random(F)*t^(Random([0..5])) : j in [1..3] ] : i in [0..n] ];
// y:=[ &+[ Random(F)*t^(Random([0..5])) : j in [1..3] ] : i in [0..n] ];

// x:=[x0,x1,x2,x3];
// y:=[y0,y1,y2,y3];

// print "f = ", f;

print "";
print "";

print "x = ", x;
print "y = ", y;

vvars:=(x cat y);
//vvars:=[];

load 'gt.m';


print "";
print "";
print "Generating primitive roots...";
time primr:=GenPrimRoots(p,n+1);
print "Done";

print "";
print "";
print "Generating binomials...";
time tab:=bin_tab(p,maxdeg,p^(n+1));
print "Done";


print "";
print "";
print "Generating eta pols...";
time pols:=etapols(p,n);
print "Done";


print "";
print "";
print "**********************************************************************";
print "First method: Use GT formula!";
t:=Cputime();
ResetMaximumMemoryUsage();
res1:=GT(f : pols:=pols, primr:=primr, tab:=tab, vvars:=vvars);
print "Time used (in seconds): ", Cputime(t);
print "Memory Usage (in MB): ", GetMaximumMemoryUsage()/((1024.0)^2);
print "**********************************************************************";



// let's convert f to an associative array to make it more efficient below
af:=AssociativeArray();
for X in f do
    af[[X[2],X[3]]]:=X[1];
end for;

print "";
print "";
print "**********************************************************************";
print "Second method: Add and multiply using the etas (precomputed).";
t:=Cputime();
ResetMaximumMemoryUsage();
res2:=[ F!0 : i in [0..n] ]; // result = 0
degX:=Max([X[1] : X in Keys(af)]); // deg in x
degY:=Max([X[2] : X in Keys(af)]); // deg in y

// vecY:=[ [ F!1 ] cat [ F!0 : i in [1..n] ] ]; // powers of y vector
vecY:=[ [ P!1 ] cat [ P!0 : i in [1..n] ] ]; // powers of y vector

// print "compute powers";
for i in [1..degY] do
    Append(~vecY,newWittProd(vecY[i],y : pols:=pols));
end for;

// XX:=[ F!1 ] cat [ F!0 : i in [1..n] ]; // power of x
XX:=[ P!1 ] cat [ P!0 : i in [1..n] ]; // power of x

for i in [0..degX] do
    for j in [t : t in [0..degY] | IsDefined(af,[i,t])] do
        tmp:=af[[i,j]];
        if tmp ne [F!0 : l in [0..n] ] then
            if i ne 0 then
                tmp:=newWittProd(tmp,XX : pols:=pols);
            end if;
            if j ne 0 then
                tmp:=newWittProd(tmp,vecY[j+1] : pols:=pols);
            end if;
            // print "compute sum";
            res2:=newWittSum(tmp,res2 : pols:=pols);
            delete tmp;
        end if;
    end for;

    // new power of x, if necessary
    if i lt degX then
        XX:=newWittProd(XX,x : pols:=pols);
    end if;
end for;
            
print "Time used (in seconds): ", Cputime(t);
print "Memory Usage (in MB): ", GetMaximumMemoryUsage()/((1024.0)^2);
print "**********************************************************************";



print "";
print "";
print "**********************************************************************";
print "Third method: Use new GT algor!";
t:=Cputime();
ResetMaximumMemoryUsage();
res3:=GT2(f : pols:=pols, primr:=primr, tab:=tab, vvars:=vvars);
print "Time used (in seconds): ", Cputime(t);
print "Memory Usage (in MB): ", GetMaximumMemoryUsage()/((1024.0)^2);
print "**********************************************************************";



print "";
print "";
print "Test res1 == res2: ", res1 eq res2;
print "Test res1 == res3: ", res1 eq res3;




/*

(p=3)

> load 'gt.m';                                                            
Loading "gt.m"                                                            
Loading "etas.m"                                                          
Loading "witt_gen.m"                                                      
Loading "witt_gen.m"                                                      
> load 'test_gt.m';                                                       
Loading "test_gt.m"                                                       
f =  [ [*                                                                 
    [ 2, 0, 1, 2 ],                                                       
    0, 0                                                                  
*], [*                                                                    
    [ 2, 1, 0, 2 ],                                                       
    0, 1                                                                  
*], [*                                                                    
    [ 2, 0, 2, 0 ],                                                       
    0, 2                                                                  
*], [*                                                                    
    [ 2, 1, 2, 1 ],                                                       
    0, 3                                                                  
*], [*                                                                    
    [ 1, 0, 1, 0 ],                                                       
    1, 0                                                                  
*], [*                                                                    
    [ 0, 1, 0, 2 ],                                                       
    1, 1                                                                  
*], [*                                                                    
    [ 2, 0, 1, 1 ],                                                       
    1, 2                                                                  
*], [*                                                                    
    [ 1, 1, 0, 2 ],                                                       
    1, 3                                                                  
*], [*                                                                    
    [ 1, 1, 1, 1 ],                                                       
    2, 0                                                                  
*], [*                                                                    
    [ 1, 2, 0, 1 ],                                                       
    2, 1                                                                  
*], [*                                                                    
    [ 0, 1, 2, 2 ],                                                       
    2, 2                                                                  
*], [*                                                                    
    [ 2, 0, 0, 0 ],                                                       
    2, 3                                                                  
*], [*                                                                    
    [ 0, 2, 1, 1 ],                                                       
    3, 0                                                                  
*], [*                                                                    
    [ 2, 0, 2, 1 ],                                                       
    3, 1                                                                  
*], [*                                                                    
    [ 2, 0, 2, 0 ],                                                       
    3, 2                                                                  
*], [*                                                                    
    [ 1, 1, 1, 2 ],                                                       
    3, 3                                                                  
*] ]                                                                      


x =  [
    x0,
    x1,
    x2,
    x3 
]      
y =  [ 
    y0,
    y1,
    y2,
    y3 
]      
Loading "gt.m"
Loading "etas.m"
Loading "witt_gen.m"
Loading "witt_gen.m"


Generating primitive roots...
Time: 0.000                  
Done                         


Generating binomials...
Time: 0.000            
Done                   


Generating eta pols...
Time: 0.000           
Done                  


**********************************************************************
First method: Use GT formula!                                         
Time used (in seconds):  25.240                                       
Memory Usage (in MB):  61.5937500000000000000000000000                
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).         
Time used (in seconds):  161.560                                      
Memory Usage (in MB):  134.593750000000000000000000000                
**********************************************************************


**********************************************************************
Third method: Use new GT algor!                                       
compute etas                                                          
Time: 1.090                                                           
compute etas                                                          
Time: 16.140                                                          
compute etas                                                          
Time: 14.400                                                          
Time used (in seconds):  32.980                                       
Memory Usage (in MB):  117.812500000000000000000000000                
**********************************************************************


(p=3)

f =  [ [*                                                                
    [ 0, 0, 1, 0 ],                                                      
    0, 0                                                                 
*], [*                                                                   
    [ 2, 0, 0, 1 ],                                                      
    0, 1                                                                 
*], [*                                                                   
    [ 2, 2, 2, 1 ],                                                      
    0, 2                                                                 
*], [*                                                                   
    [ 2, 2, 0, 0 ],                                                      
    0, 3                                                                 
*], [*                                                                   
    [ 1, 2, 1, 0 ],                                                      
    0, 4                                                                 
*], [*                                                                   
    [ 1, 1, 0, 2 ],                                                      
    1, 0                                                                 
*], [*                                                                   
    [ 0, 2, 2, 0 ],                                                      
    1, 1                                                                 
*], [*                                                                   
    [ 2, 0, 0, 2 ],                                                      
    1, 2                                                                 
*], [*                                                                   
    [ 0, 2, 1, 1 ],                                                      
    1, 3                                                                 
*], [*                                                                   
    [ 1, 0, 0, 1 ],                                                      
    1, 4                                                                 
*], [*                                                                   
    [ 2, 0, 0, 0 ],                                                      
    2, 0                                                                 
*], [*                                                                   
    [ 2, 1, 0, 0 ],                                                      
    2, 1                                                                 
*], [*                                                                   
    [ 2, 1, 2, 1 ],                                                      
    2, 2                                                                 
*], [*                                                                   
    [ 0, 0, 2, 1 ],                                                      
    2, 3                                                                 
*], [*                                                                   
    [ 1, 1, 2, 1 ],                                                      
    2, 4                                                                 
*], [*                                                                   
    [ 0, 1, 1, 2 ],                                                      
    3, 0                                                                 
*], [*                                                                   
    [ 1, 1, 0, 1 ],                                                      
    3, 1                                                                 
*], [*                                                                   
    [ 2, 2, 1, 0 ],                                                      
    3, 2                                                                 
*], [*                                                                   
    [ 0, 1, 2, 2 ],                                                      
    3, 3                                                                 
*], [*                                                                   
    [ 2, 1, 0, 0 ],                                                      
    3, 4                                                                 
*], [*                                                                   
    [ 1, 0, 1, 0 ],                                                      
    4, 0                                                                 
*], [*                                                                   
    [ 0, 2, 0, 2 ],                                                      
    4, 1                                                                 
*], [*                                                                   
    [ 2, 1, 0, 2 ],                                                      
    4, 2                                                                 
*], [*                                                                   
    [ 1, 1, 1, 1 ],                                                      
    4, 3                                                                 
*], [*                                                                   
    [ 0, 1, 1, 1 ],                                                      
    4, 4                                                                 
*] ]                                                                     


x =  [
    x0,
    x1,
    x2,
    x3 
]      
y =  [ 
    y0,
    y1,
    y2,
    y3 
]      
Loading "gt.m"
Loading "etas.m"
Loading "witt_gen.m"
Loading "witt_gen.m"


Generating primitive roots...
Time: 0.000                  
Done                         


Generating binomials...
Time: 0.000            
Done                   


Generating eta pols...
Time: 0.000           
Done                  


**********************************************************************
First method: Use GT formula!                                         
Time used (in seconds):  104.870
Memory Usage (in MB):  129.375000000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  1060.180
Memory Usage (in MB):  309.968750000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 4.680
compute etas
Time: 81.830
compute etas
Time: 57.560
Time used (in seconds):  147.640
Memory Usage (in MB):  247.593750000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true




p=3

f =  [ [*                                                                
    [ 2, 1, 1, 2 ],                                                      
    0, 0                                                                 
*], [*                                                                   
    [ 2, 2, 2, 1 ],                                                      
    0, 1                                                                 
*], [*                                                                   
    [ 1, 1, 0, 1 ],                                                      
    0, 2                                                                 
*], [*                                                                   
    [ 1, 0, 0, 0 ],                                                      
    0, 3                                                                 
*], [*                                                                   
    [ 0, 1, 0, 0 ],                                                      
    0, 4                                                                 
*], [*                                                                   
    [ 2, 0, 2, 1 ],                                                      
    0, 5                                                                 
*], [*                                                                   
    [ 2, 1, 0, 0 ],                                                      
    1, 0                                                                 
*], [*                                                                   
    [ 2, 1, 1, 1 ],                                                      
    1, 1                                                                 
*], [*                                                                   
    [ 2, 1, 0, 2 ],                                                      
    1, 2                                                                 
*], [*                                                                   
    [ 0, 2, 2, 0 ],                                                      
    1, 3                                                                 
*], [*                                                                   
    [ 0, 0, 2, 2 ],                                                      
    1, 4                                                                 
*], [*                                                                   
    [ 2, 0, 2, 1 ],                                                      
    1, 5                                                                 
*], [*                                                                   
    [ 2, 1, 0, 0 ],                                                      
    2, 0                                                                 
*], [*                                                                   
    [ 1, 1, 1, 2 ],                                                      
    2, 1                                                                 
*], [*                                                                   
    [ 0, 1, 0, 0 ],                                                      
    2, 2                                                                 
*], [*                                                                   
    [ 1, 0, 0, 0 ],                                                      
    2, 3                                                                 
*], [*                                                                   
    [ 2, 1, 0, 0 ],                                                      
    2, 4                                                                 
*], [*                                                                   
    [ 2, 0, 2, 2 ],                                                      
    2, 5                                                                 
*], [*                                                                   
    [ 2, 2, 1, 2 ],                                                      
    3, 0                                                                 
*], [*                                                                   
    [ 0, 0, 2, 0 ],                                                      
    3, 1                                                                 
*], [*                                                                   
    [ 2, 0, 0, 2 ],                                                      
    3, 2                                                                 
*], [*                                                                   
    [ 1, 1, 0, 2 ],                                                      
    3, 3                                                                 
*], [*                                                                   
    [ 2, 2, 1, 1 ],                                                      
    3, 4                                                                 
*], [*                                                                   
    [ 2, 2, 1, 0 ],                                                      
    3, 5                                                                 
*], [*                                                                   
    [ 2, 2, 2, 2 ],                                                      
    4, 0                                                                 
*], [*                                                                   
    [ 0, 1, 1, 1 ],                                                      
    4, 1                                                                 
*], [*                                                                   
    [ 2, 2, 0, 1 ],                                                      
    4, 2                                                                 
*], [*                                                                   
    [ 1, 2, 0, 2 ],                                                      
    4, 3                                                                 
*], [*                                                                   
    [ 1, 0, 2, 2 ],                                                      
    4, 4                                                                 
*], [*                                                                   
    [ 2, 1, 2, 1 ],                                                      
    4, 5                                                                 
*], [*                                                                   
    [ 1, 1, 0, 2 ],                                                      
    5, 0                                                                 
*], [*                                                                   
    [ 0, 2, 0, 2 ],                                                      
    5, 1                                                                 
*], [*                                                                   
    [ 2, 2, 0, 1 ],                                                      
    5, 2                                                                 
*], [*                                                                   
    [ 0, 2, 2, 1 ],                                                      
    5, 3                                                                 
*], [*                                                                   
    [ 1, 0, 0, 1 ],                                                      
    5, 4                                                                 
*], [*                                                                   
    [ 0, 1, 1, 2 ],                                                      
    5, 5                                                                 
*] ]                                                                     


x =  [
    x0,
    x1,
    x2,
    x3 
]      
y =  [ 
    y0,
    y1,
    y2,
    y3 
]      
Loading "gt.m"
Loading "etas.m"
Loading "witt_gen.m"
Loading "witt_gen.m"


Generating primitive roots...
Time: 0.000                  
Done                         


Generating binomials...
Time: 0.000            
Done                   


Generating eta pols...
Time: 0.000           
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  359.070
Memory Usage (in MB):  255.593750000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  6590.430
Memory Usage (in MB):  636.437500000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 15.100
compute etas
Time: 305.580
compute etas
Time: 175.480
Time used (in seconds):  503.420
Memory Usage (in MB):  547.125000000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true







###########################################################3
NUMERIC:

p=11
k=10
n=4

deg=5



x =  [
    12*a^9 + 6*a^8 + 6*a^6 + 9*a^5 + 8*a^4 + 4*a^3 + 10*a^2 + 6*a + 3,
    a^9 + 8*a^8 + 3*a^6 + 5*a^5 + 10*a^4 + 4*a^3 + 10*a^2 + 7*a,      
    a^8 + 6*a^7 + a^6 + 7*a^4 + 10*a^3 + 10*a^2 + 8*a + 2,            
    2*a^9 + 12*a^8 + 2*a^7 + 5*a^6 + 4*a^5 + 12*a^3 + 3*a^2 + a + 3,  
    12*a^9 + 12*a^8 + 12*a^7 + 6*a^6 + 9*a^5 + 9*a^4 + 8*a^3 + 10*a^2 + 10*a + 10
]                                                                                
y =  [                                                                           
    3*a^9 + 8*a^8 + a^7 + 9*a^6 + 2*a^5 + a^4 + 7*a^3 + 10*a^2 + 7*a + 5,        
    11*a^9 + 2*a^8 + 5*a^7 + 3*a^6 + 11*a^5 + 5*a^4 + 7*a^3 + 9*a^2 + 2*a + 12,  
    11*a^9 + 5*a^8 + 9*a^7 + 4*a^6 + 2*a^5 + 3*a^4 + 8*a^2 + 2*a + 7,            
    2*a^9 + 7*a^8 + 9*a^7 + 9*a^6 + 2*a^5 + 9*a^4 + 11*a^3 + 12*a^2 + 2*a + 9,   
    10*a^9 + 11*a^8 + 5*a^7 + 10*a^6 + 2*a^4 + 2*a^3 + 2*a^2 + 8*a + 2           
]                                                                                


Generating primitive roots...
Time: 0.010                  
Done                         


Generating binomials...
Time: 0.000            
Done                   


Generating eta pols...
Time: 114.920
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  8.900
Memory Usage (in MB):  17.4375000000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  39.020
Memory Usage (in MB):  19.5625000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 7.530
compute etas
Time: 1.200
compute etas
Time: 0.180
compute etas
Time: 0.040
Time used (in seconds):  9.190
Memory Usage (in MB):  17.7500000000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true


#######################################################

p=11
k=10
n=4

deg=7 

(use already computed etas from above)


x =  [
    3*a^9 + 7*a^8 + 9*a^7 + 10*a^6 + 10*a^5 + 11*a^4 + 3*a^3 + 9*a^2 + a + 1,
    3*a^9 + 4*a^8 + 6*a^7 + 2*a^6 + 4*a^5 + 8*a^4 + 11*a^3 + 9*a^2 + a + 9,  
    6*a^9 + 12*a^8 + a^7 + 4*a^5 + 5*a^4 + 11*a^3 + 4*a^2 + 2*a + 5,         
    9*a^9 + 9*a^8 + 9*a^7 + a^6 + 2*a^5 + 12*a^4 + 12*a^3 + 7*a^2 + 5*a + 8, 
    11*a^9 + 8*a^8 + 7*a^7 + 9*a^6 + 11*a^5 + 5*a^2 + 12*a + 10              
]                                                                            
y =  [                                                                       
    11*a^9 + a^8 + 7*a^7 + 10*a^6 + 8*a^5 + 10*a^4 + 2*a^3 + 2*a^2 + 11*a + 4,
    a^9 + 10*a^8 + 7*a^6 + 6*a^5 + 4*a^4 + a^3 + 11*a^2 + 7*a + 5,            
    9*a^9 + 11*a^8 + 3*a^7 + 8*a^6 + 12*a^5 + 5*a^4 + 11*a^3 + 9*a^2 + 12,    
    8*a^9 + 11*a^8 + 5*a^7 + 8*a^6 + 4*a^5 + a^3 + 3*a + 3,                   
    4*a^9 + 10*a^8 + 6*a^7 + 12*a^6 + 11*a^5 + 5*a^4 + 10*a^3 + 10*a^2 + 11*a + 6
]                                                                                
Loading "gt.m"                                                                   
Loading "etas.m"                                                                 
Loading "witt_gen.m"                                                             
Loading "witt_gen.m"                                                             


Generating primitive roots...
Time: 0.000
Done


Generating binomials...
Time: 0.000
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  16.540
Memory Usage (in MB):  15.8750000000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  70.900
Memory Usage (in MB):  17.1250000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 13.410
compute etas
Time: 2.210
compute etas
Time: 0.330
compute etas
Time: 0.070
Time used (in seconds):  16.490
Memory Usage (in MB):  15.8750000000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true


#########################################################

p:=3; // char.
k:=10; // exponent of the field
n:=6; // (lenght - 1) of Witt vectors

maxdeg:=7;

omit f


x =  [
    15*a^9 + 7*a^8 + 4*a^7 + 6*a^6 + 7*a^4 + 14*a^3 + 5*a^2 + 2*a + 3,
    14*a^9 + 8*a^8 + 8*a^7 + 5*a^6 + 14*a^5 + 2*a^4 + 7*a^2 + 8*a + 4,
    15*a^9 + 5*a^8 + 11*a^7 + 16*a^6 + 14*a^5 + 5*a^4 + 14*a^3 + 9*a^2 + 16*a + 12,
    12*a^9 + 2*a^8 + 3*a^7 + 6*a^6 + 11*a^5 + 7*a^4 + 9*a^3 + a^2 + 9*a + 12,      
    11*a^9 + 16*a^7 + 2*a^6 + 8*a^5 + 9*a^4 + 4*a^3 + 3*a + 4                      
]                                                                                  
y =  [                                                                             
    8*a^9 + 8*a^8 + 15*a^7 + 6*a^6 + 14*a^5 + 3*a^4 + a^3 + 14*a^2 + 15*a + 2,     
    15*a^9 + 2*a^7 + 5*a^6 + 9*a^5 + 12*a^4 + 15*a^3 + 3*a^2 + 14*a + 13,          
    15*a^8 + 4*a^7 + 7*a^6 + 10*a^5 + 2*a^4 + 5*a^3 + 12*a^2 + 4*a + 6,            
    5*a^9 + 3*a^8 + 3*a^7 + 11*a^6 + 14*a^5 + 2*a^4 + 8*a^3 + 16*a^2 + 2*a,        
    15*a^9 + 5*a^8 + 8*a^7 + 11*a^6 + 5*a^5 + 2*a^4 + 4*a^3 + 13*a^2 + 8*a + 10    
]                                                                                  
Loading "gt.m"                                                                     
Loading "etas.m"                                                                   
Loading "witt_gen.m"                                                               
Loading "witt_gen.m"                                                               


Generating primitive roots...
Time: 0.000
Done


Generating binomials...
Time: 0.000
Done


Generating eta pols...
Time: 1042.080
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  150.590
Memory Usage (in MB):  23.8750000000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  337.230
Memory Usage (in MB):  28.3750000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 132.930
compute etas
Time: 15.820
compute etas
Time: 1.490
compute etas
Time: 0.130
Time used (in seconds):  151.230
Memory Usage (in MB):  23.6250000000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true


######################################################

p:=3; // char.
k:=10; // exponent of the field
n:=8; // (lenght - 1) of Witt vectors

maxdeg:=15;  // max. degree of x and y


x =  [ a^14063, a^29107, a^55003, a^38186, a^34539, a^7062, a^7372, a^32605, a^9493 ]
y =  [ a^49475, a^38264, a^32604, a^35309, a^19929, a^1882, a^43111, a^46017, a^8997 ]
Loading "gt.m"                                                                        
Loading "etas.m"                                                                      
Loading "witt_gen.m"                                                                  
Loading "witt_gen.m"                                                                  


Generating primitive roots...
Time: 0.000                  
Done                         


Generating binomials...
Time: 0.000            
Done                   


Generating eta pols...
Time: 10.570
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  34.630
Memory Usage (in MB):  12.9687500000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  75.010
Memory Usage (in MB):  12.3125000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 2.980
compute etas
Time: 3.000
compute etas
Time: 3.110
compute etas
Time: 3.230
compute etas
Time: 2.990
compute etas
Time: 2.620
compute etas
Time: 2.490
compute etas
Time: 1.800
Time used (in seconds):  34.330
Memory Usage (in MB):  12.9687500000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true

######################################
p:=3; // char.
k:=10; // exponent of the field
n:=9; // (lenght - 1) of Witt vectors

maxdeg:=20;  // max. degree of x and y


Generating primitive roots...
Time: 0.000                  
Done                         


Generating binomials...
Time: 0.000            
Done                   


Generating eta pols...
Time: 108.780         
Done                  


**********************************************************************
First method: Use GT formula!                                         
Time used (in seconds):  130.280                                      
Memory Usage (in MB):  16.4062500000000000000000000000                
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).         
Time used (in seconds):  433.310                                      
Memory Usage (in MB):  13.2187500000000000000000000000                
**********************************************************************


**********************************************************************
Third method: Use new GT algor!                                       
compute etas                                                          
Time: 11.920                                                          
compute etas                                                          
Time: 12.060                                                          
compute etas                                                          
Time: 11.850                                                          
compute etas                                                          
Time: 11.990                                                          
compute etas                                                          
Time: 10.910                                                          
compute etas                                                          
Time: 9.780                                                           
compute etas                                                          
Time: 8.180                                                           
compute etas                                                          
Time: 7.860                                                           
compute etas                                                          
Time: 6.580                                                           
Time used (in seconds):  129.730                                      
Memory Usage (in MB):  16.8125000000000000000000000000                
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true


#######################################################
p, k, n, maxdeg =  19 10 4 15                                             


x =  [
    17*a^9 + 16*a^8 + 3*a^7 + 10*a^6 + 12*a^5 + 18*a^4 + 14*a^3 + 10*a^2 + 3*a + 1,
    6*a^9 + 3*a^8 + 6*a^7 + 14*a^6 + 18*a^4 + 13*a^3 + 4*a^2 + 4*a + 12,           
    14*a^9 + 10*a^8 + 18*a^7 + 8*a^6 + 16*a^5 + 16*a^4 + 16*a^3 + 5*a^2 + 18,      
    14*a^9 + 12*a^8 + 4*a^7 + 16*a^6 + 15*a^5 + 12*a^4 + 14*a^3 + 14*a^2 + 14*a + 9,
    7*a^9 + 17*a^8 + a^7 + 12*a^6 + 12*a^5 + 14*a^4 + 13*a^3 + 14*a^2 + 8*a + 6     
]                                                                                   
y =  [                                                                              
    7*a^9 + 5*a^7 + 6*a^6 + 11*a^5 + 10*a^4 + 7*a^3 + 9*a^2 + 4*a + 18,             
    17*a^8 + 15*a^7 + 9*a^6 + 15*a^5 + 4*a^4 + 10*a^3 + 16*a^2 + 15*a + 18,         
    8*a^9 + 15*a^8 + 3*a^7 + 18*a^6 + 17*a^5 + 11*a^3 + 3*a^2 + 17*a + 10,          
    18*a^9 + a^8 + 13*a^7 + 4*a^6 + 11*a^4 + 2*a^3 + 12*a^2 + 18*a + 9,             
    7*a^9 + 16*a^8 + 11*a^7 + 4*a^6 + 3*a^5 + 15*a^4 + 12*a^3 + 6*a^2 + 16*a + 8    
]                                                                                   
Loading "gt.m"                                                                      
Loading "etas.m"                                                                    
Loading "witt_gen.m"                                                                
Loading "witt_gen.m"                                                                


Generating primitive roots...
Time: 0.000
Done


Generating binomials...
Time: 0.000
Done


Generating eta pols...
Time: 2760.360
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  983.080
Memory Usage (in MB):  26.7187500000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  2301.170
Memory Usage (in MB):  32.4375000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 882.940
compute etas
Time: 96.870
compute etas
Time: 8.360
compute etas
Time: 0.640
Time used (in seconds):  993.390
Memory Usage (in MB):  26.3125000000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true

##############################################3

p, k, n, maxdeg =  13 10 5 15                                           


x =  [
    a^9 + a^8 + 10*a^7 + 11*a^6 + 4*a^5 + a^4 + 10*a^3 + 11*a^2 + a + 9,
    7*a^9 + 6*a^8 + 9*a^7 + 2*a^6 + 6*a^5 + 12*a^3 + 7*a^2 + 2*a + 7,   
    6*a^8 + 5*a^7 + 11*a^6 + 8*a^5 + 7*a^4 + 8*a^3 + 7*a^2 + 2*a + 2,   
    5*a^9 + 9*a^8 + 8*a^7 + 3*a^6 + 2*a^5 + 8*a^4 + a^2 + 8*a + 4,      
    8*a^9 + 7*a^8 + 6*a^7 + 10*a^6 + 8*a^4 + 2*a^3 + 11*a^2 + 8*a + 12, 
    9*a^9 + 8*a^8 + 6*a^7 + 7*a^6 + 2*a^5 + 6*a^4 + 6*a^3 + 4*a^2 + 10*a + 11
]                                                                            
y =  [                                                                       
    11*a^9 + 3*a^8 + 5*a^7 + 6*a^6 + a^5 + 7*a^4 + 7*a^3 + 6*a^2 + 7*a + 6,  
    a^9 + 6*a^8 + 10*a^7 + 11*a^5 + 8*a^4 + 12*a^3 + 12*a^2 + 2*a + 3,       
    6*a^9 + 12*a^8 + 2*a^7 + 10*a^6 + 12*a^5 + 12*a^4 + 10*a^3 + 10*a^2 + 2*a + 9,
    11*a^9 + 5*a^8 + 10*a^7 + 5*a^6 + 6*a^5 + 12*a^4 + 7*a^3 + 6*a^2,             
    6*a^9 + 7*a^8 + a^7 + 8*a^5 + 2*a^4 + 4*a^3 + 7*a^2 + a + 5,                  
    3*a^9 + 10*a^8 + 4*a^7 + a^6 + 2*a^5 + 9*a^4 + 10*a^2 + 6*a + 11              
]                                                                                 
Loading "gt.m"                                                                    
Loading "etas.m"                                                                  
Loading "witt_gen.m"                                                              
Loading "witt_gen.m"                                                              


Generating primitive roots...
Time: 0.000                  
Done                         


Generating binomials...
Time: 0.000            
Done


Generating eta pols...
Time: 29854.750
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  1045.080
Memory Usage (in MB):  49.0000000000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  4608.840
Memory Usage (in MB):  70.6250000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 890.010
compute etas
Time: 152.970
compute etas
Time: 21.390
compute etas
Time: 2.640
compute etas
Time: 0.680
Time used (in seconds):  1077.590
Memory Usage (in MB):  53.3437500000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true

#################################################
p, k, n, maxdeg =  7 10 6 20                                              


x =  [
    6*a^9 + 6*a^8 + 6*a^7 + 3*a^6 + 6*a^5 + 5*a^4 + 5*a^2 + a,
    3*a^9 + 2*a^6 + 3*a^5 + 6*a^4 + 4*a^3 + 3*a^2 + 4,        
    6*a^9 + 6*a^8 + a^6 + 2*a^5 + 3*a^4 + 6*a^3 + 3*a^2 + 2*a + 3,
    6*a^9 + 4*a^8 + a^7 + 2*a^6 + 6*a^5 + 4*a^4 + 5*a^3 + 2*a^2 + 4*a,
    5*a^9 + a^7 + 2*a^6 + a^5 + a^2,                                  
    2*a^9 + a^8 + 2*a^7 + a^6 + 2*a^5 + 6*a^4 + 5*a^2 + a + 4,        
    4*a^9 + 6*a^8 + 4*a^7 + 5*a^6 + 2*a^5 + 5*a^4 + a^3 + 2*a + 2     
]                                                                     
y =  [                                                                
    5*a^9 + 5*a^8 + 2*a^7 + 3*a^6 + 5*a^5 + 6*a^2 + a,                
    6*a^9 + 2*a^8 + 4*a^7 + 6*a^6 + 6*a^5 + 2*a^4 + 4*a^3 + 6*a^2 + 4,
    3*a^9 + 3*a^8 + 6*a^7 + 2*a^6 + 5*a^5 + 5*a^3 + a^2 + 2*a + 3,    
    a^9 + a^7 + 5*a^6 + 2*a^5 + a^4 + 2*a^3 + 3*a^2 + 2*a + 4,        
    a^9 + 2*a^8 + 4*a^7 + 6*a^6 + a^5 + 5*a^4 + 5*a^3 + 3*a^2 + 6*a,  
    6*a^9 + 2*a^8 + 6*a^7 + 4*a^6 + 6*a^5 + 5*a^4 + 3*a^3 + 5*a^2 + 2*a + 5,
    2*a^9 + 4*a^7 + 6*a^6 + 2*a^5 + 4*a^4 + 2*a^3 + 4*a + 4                 
]                                                                           
Loading "gt.m"                                                              
Loading "etas.m"                                                            
Loading "witt_gen.m"                                                        
Loading "witt_gen.m"                                                        


Generating primitive roots...
Time: 0.000                  
Done                         


Generating binomials...
Time: 0.000
Done


Generating eta pols...
Time: 3554.780
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  600.230
Memory Usage (in MB):  28.7187500000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  2410.490
Memory Usage (in MB):  28.0000000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 401.440
compute etas
Time: 131.390
compute etas
Time: 38.050
compute etas
Time: 9.600
compute etas
Time: 3.300
compute etas
Time: 2.060
Time used (in seconds):  609.400
Memory Usage (in MB):  27.6250000000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true

################################################

p, k, n, maxdeg =  11 10 5 20                                             


x =  [
    7*a^9 + 2*a^8 + 10*a^7 + 10*a^6 + 8*a^5 + 3*a^3 + 3*a^2 + a + 10,
    10*a^9 + a^7 + 7*a^6 + 9*a^5 + 6*a^4 + 6*a^3 + 6*a^2 + 7*a + 6,  
    7*a^9 + 8*a^8 + 6*a^7 + 9*a^6 + 5*a^5 + 10*a^4 + 6*a^3 + 5*a^2 + 9*a + 1,
    8*a^9 + 7*a^8 + 5*a^7 + a^6 + 10*a^5 + 5*a^4 + 7*a^3 + a^2 + 4*a + 8,    
    3*a^9 + 10*a^8 + 3*a^7 + 4*a^6 + a^5 + 7*a^4 + 5*a^3 + 5*a^2 + 6*a + 1,  
    3*a^8 + 4*a^7 + 9*a^6 + 6*a^5 + 10*a^4 + a^3 + 2*a^2                     
]                                                                            
y =  [                                                                       
    3*a^9 + 3*a^8 + 2*a^7 + 5*a^5 + 4*a^4 + 4*a^3 + 10*a^2 + 7*a + 4,        
    6*a^8 + 2*a^7 + 5*a^6 + 7*a^5 + 10*a^4 + 10*a^2 + 9*a + 7,               
    a^9 + 3*a^8 + 10*a^7 + 3*a^6 + 3*a^5 + a^4 + 2*a^3 + a^2 + 5*a + 5,      
    a^7 + 9*a^5 + 4*a^4 + 3*a^3 + 10*a^2 + a + 7,                            
    3*a^9 + 8*a^8 + 2*a^7 + 5*a^6 + 4*a^4 + a^3 + 8*a^2 + 2*a + 6,           
    5*a^9 + 5*a^8 + 9*a^7 + 2*a^6 + 7*a^5 + 7*a^4 + 3*a^3 + 2*a^2 + 7*a      
]                                                                            
Loading "gt.m"                                                               
Loading "etas.m"                                                             
Loading "witt_gen.m"                                                         
Loading "witt_gen.m"                                                         


Generating primitive roots...
Time: 0.000                  
Done


Generating binomials...
Time: 0.000
Done


Generating eta pols...
Time: 5794.890
Done


**********************************************************************
First method: Use GT formula!
Time used (in seconds):  839.370
Memory Usage (in MB):  30.8750000000000000000000000000
**********************************************************************


**********************************************************************
Second method: Add and multiply using the etas (precomputed).
Time used (in seconds):  3564.620
Memory Usage (in MB):  37.4375000000000000000000000000
**********************************************************************


**********************************************************************
Third method: Use new GT algor!
compute etas
Time: 613.770
compute etas
Time: 132.680
compute etas
Time: 22.630
compute etas
Time: 3.720
compute etas
Time: 1.290
Time used (in seconds):  786.370
Memory Usage (in MB):  31.6250000000000000000000000000
**********************************************************************


Test res1 == res2:  true
Test res1 == res3:  true


*/
