#13628: refactor xgcd
------------------------------------+---------------------------------------
Reporter: saraedum | Owner: AlexGhitza
Type: task | Status: needs_work
Priority: trivial | Milestone: sage-5.5
Component: basic arithmetic | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Julian Rueth | Merged in:
Dependencies: #13441, #13438 | Stopgaps:
------------------------------------+---------------------------------------
Comment (by saraedum):
The patch introduces a speed penalty for integers. Therefore I left the
method {{{_xgcd}}} in for integers for places where this really matters.
The following timings are {{{without/with}}} the patch applied.
{{{
sage: x,y=3,21
sage: timeit('x.xgcd(y)')
625 loops, best of 3: 986 ns/1.56 µs per loop
sage: timeit('x._xgcd(y)')
625 loops, best of 3: 713 ns/704 ns per loop
sage: x,y=1/3,1/21
sage: timeit('x.xgcd(y)')
625 loops, best of 3: --- --/7.92 µs per loop
sage: R.<t> = QQbar[]
sage: x,y=t-1,t^2-1
sage: timeit('x.xgcd(y)')
125 loops, best of 3: 1.17 ms/1.18 ms per loop
sage: R.<t> = PolynomialRing(GF(3),implementation="NTL")
sage: x,y=t-1,t^2-1
sage: timeit('x.xgcd(y)')
625 loops, best of 3: 80 µs/80.9 µs per loop
}}}
Notice that there was no {{{xgcd}}} method for rational numbers before
since it was defined only for {{{PrincipalIdealDomainElement}}} which
{{{FieldElement}}} does not inherit from.
Also the docstring for Integers talked about some {{{weirdness}}} that was
actually not present anymore. I checked all combinations of integers
between -20 and 20 but could not find a single case where the output of
xgcd without the {{{minimal}}} option produced something really
surprising.
If the patchbot does not find any problems, then this is ready for review.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13628#comment:3>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
