#11475: improve prime_pi (speedup + small fixes)
--------------------------------------------------+-------------------------
Reporter: rohana | Owner: was
Type: enhancement | Status:
needs_review
Priority: major | Milestone: sage-4.7.1
Component: number theory | Keywords: primes,
prime counting, prime_pi
Work_issues: | Upstream: N/A
Reviewer: Yann Laigle-Chapuy, Leif Leonhardy | Author: R. Andrew
Ohana
Merged: | Dependencies:
--------------------------------------------------+-------------------------
Comment(by rohana):
Replying to [comment:43 leif]:
> Another corner case:
> {{{
> sage: legendre_phi(1000,10^10)
>
---------------------------------------------------------------------------
> NotImplementedError Traceback (most recent call
last)
>
> /home/leif/Sage/sage-4.7.1.alpha3/devel/sage-11475v9/<ipython console>
in <module>()
>
> /home/leif/Sage/sage-4.7.1.alpha3/local/lib/python2.6/site-
packages/sage/functions/prime_pi.so in
sage.functions.prime_pi.legendre_phi (sage/functions/prime_pi.c:5888)()
>
> /home/leif/Sage/sage-4.7.1.alpha3/local/lib/python2.6/site-
packages/sage/functions/prime_pi.so in
sage.functions.prime_pi.legendre_phi (sage/functions/prime_pi.c:5517)()
>
> NotImplementedError: computing legendre_phi for a > prime_pi(2^32-1) not
implemented
> sage:
> }}}
> (The message is a bit misleading by the way, since we limit '''`x`''' to
64 bits, and therefore the result is independent of `a >= 2^32`. If at
all, I'd also give the numerical upper limit for `a`, i.e. 203280221. But
as I said, there isn't really any limit on `a`.)
Of course, I wrote the method as a wrapper for __phi, so I was mainly
thinking of what I needed to call that method. I can easily remove this
bound.
>
> Also, '''don't try this at home''':
> {{{
> sage: time legendre_phi(1000,10^8)
> }}}
> (I fortunately could kill the process before the almost freezed machine
went out of swap space. Apparently computing the list of primes is
uninterruptable, which worsens the situation.)
When fixing the above issue, I can fix this. This same issue will appear
for very large `x` for `prime_pi`, this can be blamed on PARI -- it stores
the primes inefficiently and will use ~17GB for a sieve up to `2**32-1`
(my code should use ~1GB at this size). I can implement a custom sieve if
it this poses much of an issue (eventually though something needs to be
done to fix `prime_range`).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11475#comment:46>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
