#15429: Inverses in ZP are very slow
---------------------------+----------------------------------------------
Reporter: afiori | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.13
Component: performance | Keywords: p-adic inverse performance
Merged in: | Authors: Andrew Fiori
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
---------------------------+----------------------------------------------
One would probably expect that taking inverses in Zp and Qp would be of
similar speeds given that they are represented by the same class and the
call uses the same functions. This is far from the case:
{{{
sage: prim=primes_first_n(100000)
sage: p=next_prime(prim[99999])
sage: QP=Qp(p,30)
sage: ZP=Zp(p,30)
sage: ZPrim = [ZP(p) for p in prim]
sage: QPrim = [QP(p) for p in prim]
sage: %timeit [z.__invert__() for z in ZPrim]
1 loops, best of 3: 5.24 s per loop
sage: %timeit [z.__invert__() for z in QPrim]
1 loops, best of 3: 302 ms per loop
}}}
The problem is that the fraction_field function is very slow.
One cause of this is that the function _modified_print_mode is slow.
Performing the modification to this function as in the patch we obtain:
{{{
sage: %timeit [z.__invert__() for z in ZPrim]
1 loops, best of 3: 4.14 s per loop
}}}
which is still unreasonable. Consequently I have switched fraction_field
(and integer_ring) to be cached methods. The result is:
{{{
sage: %timeit [z.__invert__() for z in ZPrim]
1 loops, best of 3: 389 ms per loop
}}}
The code still typically under performs the Qp version, but not nearly as
significantly.
As a consequence, it is likely that in addition to what is currently in
the proposed patch, we would want to rewrite inverse_of_unit to not rely
on the inverse function + a cast as this is needlessly slower than a
direct implementation would be.
--
Ticket URL: <http://trac.sagemath.org/ticket/15429>
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/groups/opt_out.
