Comment #1 on 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
/usr/bin/time python -c 'from sympy import primepi; print primepi(50000000)'
|| Time (s) || Memory (MB) || What
|| 20.40 || 808388 || master
|| 2.14 || 312556 || rwh count (no numpy)
|| 0.82 || 49680 || rwh_count (numpy)
|| 4.62 || 81628 || MPU: pure Perl sieve
|| 0.067 || 8860 || MPU: pure Perl Lehmer
|| 0.021 || 8500 || MPU: Perl + C sieve, no tables
|| 0.00022 || 8420 || MPU: Perl + C sieve, table speedup
|| 0.00022 || 8428 || MPU: Perl + C Lehmer
Various times and memory from Perl's Math::Prime::Util implementation
included for comparison. Unfortunately the sizes that make MPU interesting
are far too large for the implementation on master.
Here is the code timed above:
{{{
def _rwh_pc(n):
"""Input n>=6, Returns the count of primes, 2 <= p <= n """
# Code by Robert William Hanks, see:
#
http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
n += 1
from sympy.external import import_module
np = import_module('numpy', min_python_version=(2, 6))
if np:
sieve = np.ones(n/3 + (n%6==2), dtype=np.bool)
for i in xrange(1,int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k/3 ::2*k] = False
sieve[k*(k-2*(i&1)+4)/3::2*k] = False
return 1 + np.count_nonzero(sieve)
else:
n, correction = n-n%6+6, 2-(n%6>1)
sieve = [True] * (n/3)
for i in xrange(1,int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k/3 ::2*k] = [False] *
((n/6-k*k/6-1)/k+1)
sieve[k*(k-2*(i&1)+4)/3::2*k] = [False] *
((n/6-k*(k-2*(i&1)+4)/6-1)/k+1)
return 2 + sum(sieve[1:n/3-correction])
}}}
primepi() is then modified to handle n in 2-6 as well as < 2, and then
calls _rwh_pc(n). The downside is that repeated calls don't get sped up.
I view this as more of a proof of concept that we can improve things quite
a bit without working too hard.
--
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.
