#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):
Replying to [comment:27 GeorgSWeber]:
> I admit I haven't looked at the "parallel processing" parts of the code.
But my feeling is we should proceed step-by-step now, i.e. integrate into
Sage some first version, and after that, (re-)add functionality/goodies
that had to be postponed in the course of doing so.
>
> For now, AFAIK, postponed topics are the integration (as a choice) of
the Legendre code from Andrew, the LMO code, and the parallel processing
ability.
One piece of functionality that I would like to suggest (either for myself
or anyone else interested in it) to add after everything else is done is a
cache of previous results used to optimize later calculations (instead of
just the previous result as is the case now). For example if you
calculate the nth prime (and obtain x), a later calculation of the
(n-10)-th prime, or of prime_pi(x+205) would use this result to reduce the
necessary calculation. The cache might be some sort of tree where you can
obtain a nearby previously calculated value. It would be necessary to
keep a queue of the order that cached values were used, so that the oldest
could be thrown out when the alloted storage is consumed and a new value
is to be stored in the queue. It would probably be a good idea to have
some way of not caching many values that are excessively close together,
so it might be necessary to keeps track of the statistics of how close
together the values in the cache are to determine when it is worth it to
cache a value. Maybe this cache could even be stored to disk.
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:29>
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.
