Status: New
Owner: ----
Labels: Type-Defect Priority-Medium
New issue 3922 by dana.jac...@gmail.com: primepi is slow and takes too much
memory
http://code.google.com/p/sympy/issues/detail?id=3922
primepi (prime_count) is fine for small values, but middling size numbers
like 10 million are quite slow, and larger values like 10e9 are only
possible on machines with more than 32GB.
Note that the current system generates all the primes up to the limit, then
counts them, so using timeit is problematic as it ignores the large cost to
run it the first time and only reports the fast lookups.
There are some relatively straightforward changes that should be able to
speed this up 10-30x, and help a little with the memory use.
Once done with that, there are a some other possibilities if we want more
speed. (1) segmented sieve, (2) tables to speed up counts, (3) Lehmer's
method or LMO, which will be much faster for very large values.
Lastly, fast primecount + (Li or Riemann R) can be used to speedup prime()
(SymPy's nth_prime function). We ought to be shooting for on the order of
1 second and under 100MB to compute the 100 millionth prime.
--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings
--
You received this message because you are subscribed to the Google Groups
"sympy-issues" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sympy-issues+unsubscr...@googlegroups.com.
To post to this group, send email to sympy-issues@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy-issues.
For more options, visit https://groups.google.com/groups/opt_out.
