#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.4
Component: number theory | Keywords: primes, sieve, table,LMO
Author: Kevin Stueve | Upstream: N/A
Reviewer: was,robertwb,GeorgSWeber | Merged:
Work_issues: |
----------------------------------------+-----------------------------------
Comment(by leif):
Replying to [comment:50 kevin.stueve]:
> Why not store much denser data than 1e19(1e15)2^64^? Why not store
1e19(1e9)2^64^?
:D If I was able to ''sieve'' such a large interval in reasonable time, I
wouldn't mind storing terabytes of data (including more than just pi(x)).
I think the primary goal should be getting denser tables in the whole
64-bit range, s.t. the average time for arbitrary values drops down
significantly.
This can be accompanied by sieving "from scratch" while recording more
information if we have the resources to do so.
But the current situation is that we have large "holes" in our tables that
make the combinatorial method outperform table look-up and sieving by
orders of magnitude (though taking even "too long" from a user's
perspective, i.e. up to ''hours'').
Computing pi(N*10^15^) for N>10000 is just a ''first step'', perhaps
followed by computing pi(N*10^14^) where these values are missing, and so
on, until - ''perhaps large-scale distributed'' - ''sieving'' the
remaining smaller intervals beats individually computing lots of values in
them. Anyway, having data points independently computed with other methods
is always good, and a prerequisite for validating results computed only
once.
-Leif
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:51>
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.
