#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.1
Component: number theory | Keywords: primes, sieve, table,LMO
Work_issues: | Author: Kevin Stueve
Upstream: N/A | Reviewer: was,robertwb,GeorgSWeber
Merged: |
-----------------------------+----------------------------------------------
Comment(by leif):
I would not even bother storing 16-byte pairs of (n,pi(n)), or preferably
(n,nth_prime) because it is injective, in plain (uncompressed) binary
format.
The whole range up to 2^64^ at steps of 10^9^ fits on a (DL-)DVD, and
sieving a whole interval (worst case) with 10^9^ primes today takes at
most a few minutes. (With a step size of 10^10^, the table would fit on a
CD, 10^11^ would be about 65MB and so on. The tables should compress well
for shipping because of the monotonicity.)
But we are yet far away from having such dense (and complete) tables,
though I expect (wishful thinking?) the 64-bit range to be fully sieved
within the next 5-10 years.
Regarding that, it would at my opinion be better to use a format that
allows the tables to be successively updated (i.e. extended) with
"arbitrary" intermediate values, until they one day are complete (and can
be indexed directly rather than binary-searched).
As Kevin stated, harddisks get larger and cheaper, bandwidth continuously
grows... Since the tables should be optional anyway (and they are still
quite small), I think we shouldn't be too much concerned about file sizes.
[Admins, take mercy on me...]
Of course we could support (and provide) both types of tables and let the
user choose which one is more appropriate to him (or her).
-Leif
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:39>
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.
