#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.7.1
Component: number theory | Keywords: primes, sieve,
table,LMO
Work_issues: | Upstream: N/A
Reviewer: was,robertwb,GeorgSWeber | Author: Kevin Stueve
Merged: | Dependencies:
----------------------------------------+-----------------------------------
Comment(by kevin.stueve):
I have posted new table-based prime counting code in
table_based_prime_pi_23_July_2011.zip. In addition to counting primes,
this code can also count twin primes, prime triplets, and prime
quadruplets. Since my last contribution, denser tables of the prime
counting function and counts of prime constellations have become available
(by a factor of 10 in some intervals), decreasing the amount of sieving
needed by such a factor.
This code fixes the problems in my original contribution. The sieve I
used in my original contribution was Tomás Oliveira e Silva's
prime_sieve.c, which assumed pointers have 4 bytes. The sieve I use in my
new code is Kim Walisch's primesieve. Primesieve uses portable c++ and
uses Oliveira e Silva's algorithm for large x.
Although a lot of work has been done, my code should still be considered a
rough draft. The path to the primesieve package is still hard-coded. A
second person should fix such problems and also go over the code line by
line and double-check for off-by-one errors and the like. I am willing to
offer someone who can can get this code in Sage coauthorship of the code.
This code checks for the presence of prime count tables in
SAGE_ROOT/data/prime_counting_tables, and if they are not there, instructs
the user to download them from
http://sage.math.washington.edu/home/kstueve/prime_pi_tables/.
The code communicates with primesieve using the subprocess module and
primesievesubprocess.cpp, a file I wrote to allow the code to communicate
with primesieve over the command line. It may be desirable to change this
arrangement. For one thing, primesieve has to do its initialization for
every call to table_based_prime_pi.
To build primesievesubprocess.cpp, I put it into the main primesieve
folder. I ran the primesieve make file. I removed main.o,
ParallelPrimeSieve.o, and test,o from the out folder. I then ran:
g++ primesievesubprocess.cpp out/*.o -o primesievesubprocess
Sincerely,
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:54>
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.
