#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:
--------------------------------------------------+-------------------------
Changes (by leif):
* reviewer: => Yann Laigle-Chapuy, Leif Leonhardy
Comment:
So far passed all [long] tests on Ubuntu 7.10 x86 (Sage 4.7) and Ubuntu
9.04 x86_64 (Sage 4.7.1.alpha3; patch to `module_list.py` applies with 1
line offset).
That's of course a bit funny (I don't mind):
{{{
sage: legendre_phi(2^63,0)
computation of legendre_phi for large x can take minutes, hours, or days
depending on the size of x
computation of legendre_phi for x >= 10^15 has not been thoroughly tested,
be cautious of the result
9223372036854775808
sage:
}}}
We may also add "''or weeks''", but the current version is faster than the
previous ones and '''much''' faster than the current version in Sage of
course (not to mention its odd limitation).
There are opportunities for further improvements (e.g. copying the whole
list of primes when we need more; perhaps some more comments /
documentation), but these can IMHO be left to follow-up tickets.
In principle positive review from me (minus the typos), just hesitating to
give it at this point without having studied the code more thoroughly.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11475#comment:42>
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.
