#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:46 rohana]:
> Replying to [comment:43 leif]:
> > (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`.
Ouch. (Or should it read 1.7 GB, with ~8 bytes per prime? Otherwise there
would be a real hardware limit - max. 2 or 4 GB address space - on 32-bit
machines and OSs I haven't yet met during the tests.)
I thought the huge memory consumption was mostly the fault of
`prime_range()` (and Python), and to some extent of having up to three or
four lists or arrays of primes at the same time (PARI + Python + perhaps
two Cython arrays while copying).
Would using Python ints (`py_ints=True` parameter to `prime_range()`)
alleviate the situation in any way?
One could also request the primes in chunks rather than the whole interval
at once, or implement some generator class or function that calls PARI.
Using `sage_realloc()` would also reduce the (peak) physical memory
requirement.
[[BR]]
> I can implement a custom sieve if this poses much of an issue
(eventually though something needs to be done to fix `prime_range`).
Hmmm. I thought we could avoid using `prime_range()` ''later'', on a
follow-up, e.g. by directly accessing PARI from Cython. But feel free to
implement or use some other sieve / function.
At least potentially freezing the machine (which IMHO is an OS problem)
isn't very user-friendly, especially in educational software I think...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11475#comment:47>
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.
