Opened 6 years ago

Last modified 7 weeks 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)

PadicInverse.patch (4.2 KB) - added by afiori 6 years ago.

Download all attachments as: .zip

Change History (5)

Changed 6 years ago by afiori

comment:1 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:2 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:3 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:4 Changed 7 weeks ago by chapoton

on 8.8.b7:

sage: %timeit [z.__invert__() for z in QPrim]
10 loops, best of 5: 176 ms per loop
sage: %timeit [z.__invert__() for z in ZPrim]
1 loop, best of 5: 506 ms per loop
Note: See TracTickets for help on using tickets.