#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: |
-----------------------------+----------------------------------------------
Changes (by kevin.stueve):
* cc: rohana (added)
Comment:
Andrew (rohana),
I obtained the li_approx code via a personal communication (email) from
Fredrik Johansson, owner of the mpmath project. It computes an
approximation to the logarithmic integral using an asymptotic series. You
can also find it described at
http://en.wikipedia.org/wiki/Logarithmic_integral_function#Asymptotic_expansion
I first used the Sage Li function, but switched to this one because it is
orders of magnitude faster. The Sage Li function spends unnecessary
cycles calculating Li out to many decimal places. For this application,
we can stop at the decimal point, because we only need an approximation.
Note that the calculation of an exact value of li would probably use the
series representation of li rather than the asymptotic series.
http://en.wikipedia.org/wiki/Logarithmic_integral_function#Series_representation
For large computations, the difference in time between Li and li_approx is
negligible compared to the total computation time. However, for small
computations, the saved time could be the limiting factor in the time
complexity of this algorithm. This is especially apparent when generating
the tables. Because speed is one of the most important factors in this
program, I strongly advocate keeping li_approx rather than using Sage's
exact Li. IMHO,the simplicity of calling a preexisting library function
simply does not outweigh the time trade-off of using the asymptotic
series. If anything, I would want some sort of fast li_approx to be made
a permanent part of the Sage function library, as it would be useful for
number theory research. If using exist parts of the Sage library is
desired over using new code, it might be possible to optimize small
prime_pi calculations to not depend on li, but I see this as very
unnecessary extra work.
If the sage-devel team decides that they want to use Li for its simplicity
over the asymptotic series provided by Fredrik Johansson (actually in any
case), I would like to stress the importance of using the same prime_pi
approximation function (whether li_exact or li_approx) when generating the
tables and when using them. It is absolutely critical that every detail,
including but not limited to rounding versus truncating and what the last
included term of the series is is exactly the same in both calculations
(generating the table and using it).
For everyone involved I would like to mention to be careful about
confusing the logarithmic integral and offset logarithmic integral.
For everyone to read, here is a link to my writeup (I also created an
attachment):
http://www.wstein.org/projects/stueve.pdf
After the code is added to Sage, I intend to submit the paper (most likely
with revisions/additions) for publication. As Andrew is taking part in
the development of the code and sharing authorship, I believe it would be
appropriate for myself, Andrew Ohana, and William Stein to share
authorship of both the code added to Sage and the paper submitted for
publication.
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:15>
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.
