#7013: [with patch, needs work] prime_pi and nth_prime
-----------------------------+----------------------------------------------
Reporter: kevin.stueve | Owner: kevin.stueve
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3
Component: number theory | Keywords: primes, sieve, table,LMO
Work_issues: | Author: Kevin Stueve
Upstream: N/A | Reviewer: was,robertwb,GeorgSWeber
Merged: |
-----------------------------+----------------------------------------------
Comment(by rohana):
Kevin,
I agree that the built in Li function is slower, my tests:
Built in Li:
{{{
sage: timeit('prime_pi(10**16)')
625 loops, best of 3: 809 µs per loop
sage: time prime_pi(10**16-10**10)
CPU times: user 56.95 s, sys: 0.42 s, total: 57.37 s
Wall time: 57.41 s
279238071526960
}}}
Using li_approx:
{{{
sage: timeit('prime_pi(10**16)')
625 loops, best of 3: 22.3 µs per loop
sage: time prime_pi(10**16-10**10)
CPU times: user 57.10 s, sys: 0.40 s, total: 57.50 s
Wall time: 57.54 s
279238071948684
}}}
I don't know if the li_approx is necessary, while for certain values we
have a magnitude of difference in complexity, we still are running fast
enough, and the values where time actually matters changing to Li has
little effect. We would need to fix the offset, but that shouldn't change
the runtime noticeably. If you still want to use a li_approx, I would
suggest creating a li module, and include arbitrary digit precision.
George,
I am not very familiar with C, I know that on most platforms `sizeof(long)
== sizeof(void *)`, but I don't believe this is true on all platforms, so
we might want to check the declaration of `m` as well. I'm unsure what
your comment on the tables was all about, to me SAGE_ROOT/data seemed to
be the most appropriate place to put them. Given my relatively limited
knowledge of C, I would be hesitant to join a maintenance team, but
placing prime_sieve into a spkg is clearly ideal, so if I am needed I can
join (although, I don't know how much help I would be).
Take care,
Andrew
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:16>
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.
