#18461: Implement Field._gcd_univariate_polynomial()
-------------------------------------+-------------------------------------
Reporter: pbruin | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.8
Component: basic arithmetic | Resolution:
Keywords: polynomial gcd | Merged in:
Authors: Peter Bruin | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/pbruin/18461-Field_gcd_univariate_polynomial|
908ace780e3545fec31175c6040520403e60fefd
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by pbruin):
I just tested again with the following setup:
{{{
R.<x> = RR[]
z = R.zero()
f = x^2 + 3
g = x^3 + 5
}}}
With this branch (i.e. with `Field._gcd_univariate_polynomial`):
{{{
sage: %timeit z.gcd(z)
The slowest run took 37.08 times longer than the fastest. This could mean
that an intermediate result is being cached
1000000 loops, best of 3: 1.77 µs per loop
sage: %timeit x.gcd(z)
The slowest run took 22.57 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 4.34 µs per loop
sage: %timeit z.gcd(x)
The slowest run took 66.36 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 10.5 µs per loop
sage: %timeit x.gcd(x)
The slowest run took 13.64 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 11.1 µs per loop
sage: %timeit f.gcd(g)
The slowest run took 24.83 times longer than the fastest. This could mean
that an intermediate result is being cached
10000 loops, best of 3: 33.6 µs per loop
}}}
With this branch after removing `Field._gcd_univariate_polynomial`:
{{{
sage: %timeit z.gcd(z)
The slowest run took 16.42 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 6.81 µs per loop
sage: %timeit x.gcd(z)
The slowest run took 92.70 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 11.4 µs per loop
sage: %timeit z.gcd(x)
The slowest run took 15.38 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 19.2 µs per loop
sage: %timeit x.gcd(x)
The slowest run took 4.43 times longer than the fastest. This could mean
that an intermediate result is being cached
10000 loops, best of 3: 19.9 µs per loop
sage: %timeit f.gcd(g)
The slowest run took 4.04 times longer than the fastest. This could mean
that an intermediate result is being cached
10000 loops, best of 3: 42.7 µs per loop
}}}
I don't have an explanation for the discrepancy between the slowest and
fastest runs; as far as I know there is no caching.
For complicated polynomials, the difference is undoubtedly smaller because
most time is spent in `quo_rem`, which is not touched by this branch.
--
Ticket URL: <http://trac.sagemath.org/ticket/18461#comment:4>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" 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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
