#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:47 leif]:
> Using `sage_realloc()` would also reduce the (peak) physical memory
requirement.
How long has sage had `sage_realloc`? I could have sworn that it didn't
exist a year ago.
> > 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.
I have am working on v10, which will primarily change the `__sieve`
function to directly access PARI and use `sage_realloc`. I have this
working on 64-bit linux right now:
{{{
sage: get_memory_usage()
844.1484375
sage: time legendre_phi(1000,10^8)
1
Time: CPU 22.55 s, Wall: 22.54 s
sage: get_memory_usage()
1406.78515625
}}}
Obviously I haven't made all the changes that I need to with
`legendre_phi`, however it removes the potentially insane memory issues
with using `prime_range`. Worst case scenario for storage now:
{{{
sage: time legendre_phi(1000, 203280221)
1
Time: CPU 46.85 s, Wall: 46.86 s
sage: get_memory_usage()
1975.58203125
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11475#comment:49>
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.
