Opened 6 years ago
Last modified 8 months ago
#15429 new enhancement
Inverses in ZP are very slow
Reported by: | afiori | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | performance | Keywords: | p-adic inverse performance |
Cc: | roed | Merged in: | |
Authors: | Andrew Fiori | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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.
Attachments (1)
Change History (5)
Changed 6 years ago by
comment:1 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:2 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:3 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
on 8.8.b7: