#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 leif):
Replying to [comment:47 leif]:
> Replying to [comment:46 rohana]:
> > 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`.
That might have been the case with older PARI versions; if I do
{{{
sage: time pari.init_primes(2^32)
Time: CPU 13.42 s, Wall: 18.47 s
}}}
the whole process just occupies about 283 MB (89 MB thereof basic Sage).
And yes, all have been computed, as one can "verify" with e.g. the time it
takes to get some primes around the current "end":
{{{
sage: prime_range(2^32,2^32+100) # immediate answer if init_primes(2^32)
has been called in advance
[4294967311, 4294967357, 4294967371, 4294967377, 4294967387, 4294967389]
}}}
The fatal things are commands like this:
{{{
sage: prime_range(2^30)[-1]
}}}
which turns the relative prime offsets stored by PARI (hardly more than
one byte per prime on average) into a list of boxed integers.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11475#comment:48>
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.
