There are 3 implementations of pseudoDivide:
The default one in UnivariatePolynomialCategory
(SUP uses this one);
One in PRS;
One in NewSparseUnivariatePolynomial.
A benchmark:
(1) -> )time on
(1) -> x:=reduce(+,[random(n)*monomial(1,n)$SUP(INT) for n in 1..2000]);
Type:
SparseUnivariatePolynomial(Integer)
Time: 0.01 (IN) + 0.06 (EV) + 0.03 (OT) = 0.10
sec
(2) -> y:=reduce(+,[random(n)*monomial(1,n)$SUP(INT) for n in 1..1000]);
Type:
SparseUnivariatePolynomial(Integer)
Time: 0.04 (EV) + 0.00 (OT) = 0.04
sec
(3) -> pseudoDivide(x,y)$SUP(INT);
Type: Record(coef: Integer,quotient:
SparseUnivariatePolynomial(Integer),remainder:
SparseUnivariatePolynomial(Integer))
Time: 0.00 (IN) + 4.76 (EV) + 0.02 (OT) = 4.78
sec
(4) -> pseudoDivide(x,y)$PRS(INT,SUP(INT));
Type: Record(coef: Integer,quotient:
SparseUnivariatePolynomial(Integer),remainder:
SparseUnivariatePolynomial(Integer))
Time: 0.00 (IN) + 2.44 (EV) + 0.02 (OT) = 2.46
sec
(5) -> pseudoDivide(x::NSUP(INT),y::NSUP(INT))$NSUP(INT);
Type: Record(coef: Integer,quotient:
NewSparseUnivariatePolynomial(Integer),remainder:
NewSparseUnivariatePolynomial(Integer))
Time: 0.01 (IN) + 2.93 (EV) + 0.02 (OT) = 2.96
sec
You see, the one from PRS is the fastest.
And since NSUP and SUP have same Rep, and PRS operates
on UnivariatePolynomialCategory, there is no reason that
these 3 implementations can't be merged into one.
I think the right place to implement pseudoDivide is
UnivariatePolynomialCategory, but implement in a
package and call from UnivariatePolynomialCategory
is also OK to me.
Implement in category means you have to use abstracted
constructor and selector (degree P vs. P.first.k), but I think
that doesn't slow down the algorithm much.
(On the other hand, I think there is only one Rep for
polynomials in FriCAS essentially, and only domain
essentially (SUP), so implement in SUP or UPOLYC
doesn't make much difference for now?)
What's your opinion?
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
