Sage: Ticket #15429: Inverses in ZP are very slow
https://trac.sagemath.org/ticket/15429
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
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:
</p>
<pre class="wiki">sage: %timeit [z.__invert__() for z in ZPrim]
1 loops, best of 3: 4.14 s per loop
</pre><p>
which is still unreasonable. Consequently I have switched fraction_field (and integer_ring) to be cached methods. The result is:
</p>
<pre class="wiki">sage: %timeit [z.__invert__() for z in ZPrim]
1 loops, best of 3: 389 ms per loop
</pre><p>
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.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15429
Trac 1.1.6afioriSun, 17 Nov 2013 00:31:36 GMTattachment set
https://trac.sagemath.org/ticket/15429
https://trac.sagemath.org/ticket/15429
<ul>
<li><strong>attachment</strong>
set to <em>PadicInverse.patch</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/15429#comment:1
https://trac.sagemath.org/ticket/15429#comment:1
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/15429#comment:2
https://trac.sagemath.org/ticket/15429#comment:2
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/15429#comment:3
https://trac.sagemath.org/ticket/15429#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketchapotonSat, 01 Jun 2019 08:58:35 GMT
https://trac.sagemath.org/ticket/15429#comment:4
https://trac.sagemath.org/ticket/15429#comment:4
<p>
on 8.8.b7:
</p>
<pre class="wiki">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
</pre>
Ticket