#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 kevin.stueve):
Andrew,
First of all, great work on the patch Andrew. You have done good work,
and it is nice to have the code in Cython now. I am glad to share this
project with you. I am looking forward to working more
But I have an issue with removing the fast Li approximation.
The use of fast Li approximation function for this program is absolutely
essential. I am very strongly opposed to switching out the Li
approximation for the slower built-in exact Li as it will severely impact
its average case time complexity.
You say that the cases where Li's speed matter do not affect average case
time complexity. Computing average case time complexity is difficult
because it requires that you define a probability distribution over the
possible inputs.
If the probability distribution is uniform, meaning that any input is just
as likely, then most of the input will be large numbers. For an average
large value of x (say a random 12 digit number), the li calculation takes
up a very negligible fraction of the total computation time of prime_pi.
I believe that a uniform distribution in the logarithmic domain is a more
accurate model of input probabilities. In modeling average case time
complexity, I would assume that 1, 2, 3, 4, ..etc digit numbers have equal
probabilities of being input in the program.
For small values of x (say only a few digits long), the li calculation
could represent the majority of the calculation time (where only minimal
or no sieving is needed).
When average case time complexity is modeled using the more realistic
logarithmic model, the performance of prime_pi on smaller values is not
negligible, and could represent a significant fraction of expected input.
I see no logical reason to take code that has been painstakingly optimized
for speed and make it up to 40 times slower for a significant percentage
of its expected input.
After this prime_pi and nth_prime are formally added to Sage, I would like
to create a graph of its performance for a set of random 1, 2, 3, 4... etc
digit numbers (and compare the performance to other implementations of the
prime counting function). I really, really don't want the section of the
graph representing numbers less than 5 digits to be up to 40 times slower
than it could have been because of an unfounded prejudice against the
asymptotic series for the logarithmic integral (which was written by an
expert in coding arithmetic functions and is well documented and known by
the mathematics community).
Math/Programming is war. Every cycle of speed is fought for. Don't give
it up.
Why would I want to use arbitrary precision arithmetic to calculate an
approximation that is desired to be as fast as possible (maybe you are
just advocating that the desired accuracy be a parameter)? I don't
believe that the asymptotic series lends itself to error analysis or
arbitrary precision. It is simply a fast way to calculate an
approximation. And I think that the asymptotic series is preferable here
to the series representation (with specified precision) because of speed
issues.
If I am going to make a Li module, with the exact li, an arbitrary
precision li, a specified precision li, and a fast asymptotic series li,
then I am going to need some assistance from someone who has more
experience than myself at making Sage patches (any takers?).
A would also like to mention track ticket 7017 at this time (prime range
problem). Ticket 7017 should help making plots of prime_pi.
Sincerely,
your friend,
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:17>
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.
