First to load the new function you need to unpack the library, and be sure the path is in your libname, then type:
> readlib(DGCD):
The usage of DGCD is identical to that of gcd (i.e. the additional arguments for the cofactors, etc.)
Now for the comparison, we choose two dense degree 20 polynomials in 2 variables as cofactors with a degree 20 gcd (usually the worst case):
> a:=randpoly([x,y],degree=20,dense):
> b:=randpoly([x,y],degree=20,dense):
> g:=randpoly([x,y],degree=20,dense):
> A:=expand(a*g): B:=expand(b*g):
> t:=time(): g1:=DGCD(A,B): time()-t;
1.021
> t:=time(): g2:=gcd(A,B): time()-t;
1.719
So not much difference. Try three variables, degree 10:
> a:=randpoly([x,y,z],degree=10,dense):
> b:=randpoly([x,y,z],degree=10,dense):
> g:=randpoly([x,y,z],degree=10,dense):
> A:=expand(a*g): B:=expand(b*g):
> t:=time(): g1:=DGCD(A,B): time()-t;
2.449
> t:=time(): g2:=gcd(A,B): time()-t;
27.141
Improvement is much more noticeable here.
In general the new algorithm will
out perform the old whenever the inputs are dense in the input variables.
A more general fast gcd algorithm
is in progress that will improve both dense and sparse gcd computation.