#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.8
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 uploaded a new version of the table-based prime_pi algorithm to
http://sage.math.washington.edu/home/kstueve/prime_pi_tables/table_based_prime_pi_31Dec2011.
The new version has denser tables of prime_pi and prime_pi2 (the twin
prime counting function) and higher tables of prime_pi2 than the previous
version. The new version uses a Cython wrapper around primesieve rather
than calling primesieve using the subprocess module. Despite progress
made, the code is still not yet complete. It works on my MacBook Pro (but
OpenMP only allows a single thread), but I have been unable to get
primesieve to build as a Sage component on the sage.math computer
(primesieve is portable c++, I have been able to get primesieve to build
on sage.math, just not as a Sage component). The issue surrounds enabling
OpenMP.
I also experimented with compression schemes. Given a sequence of
differences between successive errors of a logarithmic integral
approximation (I implemented Ramanujan's formula in double precision,
equation 15 at http://mathworld.wolfram.com/LogarithmicIntegral.html), for
each difference, given the highest 0 to 4 bits of the difference, by
storing the probability that the next bit will be a 1 and providing this
probability to an arithmetic coder (I used the arithmetic coder in Matt
Mahoney's paq8hp6s), you can decrease the size of the file by 16%. By
using the previous difference to predict the current difference, even more
compression may be possible- however hard-coding probabilities for the
next bit to be a 1 given the high bits of the current and previous
difference will not work-experimentally it is more efficient to allocate
the storage to the current difference rather than the previous difference.
Fitting a function such as a multivariate Gaussian to the data may be a
solution.
Hopefully the table-based prime_pi will make it into Sage in 2012.
Happy New Year,
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:55>
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.
