id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
15429,Inverses in ZP are very slow,afiori,,"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.",enhancement,new,major,sage-6.4,performance,,p-adic inverse performance,roed,,Andrew Fiori,,N/A,,,,,