Comment #41 on issue 3809 by dana.jac...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I have a fork with a complete rewrite. I need to do more testing before
doing a pull request. I'm not sure what the normal review process is -- do
a pull request and go from there, or point to a branch to get initial
comments. This includes things like whether to make some functions private
or public (e.g. modular Lucas sequence).
I've been testing on a machine that doesn't have gmpy or gmpy2, so pow()
and friends are quite slow. I'm sure there is more room for optimization.
It does make performance more visible.
The standard, strong, and extra strong Lucas tests are implemented and I've
verified that the initial pseudoprimes match the OEIS sequence and other
code.
I put some new tests in, including the two Arnault composites. I saw one
of the Arnault composites in the test suite already, but asserted as prime
with no comments. I'm not sure if this was a mistake or someone putting in
an expected defect without commenting it as such. I did not add specific
tests for the new functions.
This has deterministic tests for up to 2^64, and some more trivial factor
checking. No more _pseudos table or testing for _mr_safe. However one of
the tests I need to do is verify that we properly determine all the PSP-2's
from Feitsma's database.
for i in xrange(5000000):
if isprime(i)
sum += i
master: 25.2s
branch: 14.9s
isprime( 10**2000 + 4561 ):
44.3s old isprime using 46 bases
5.3s strong BPSW plus an extra M-R test with random base
4.3s extra strong BPSW plus an extra M-R test with random base
4.1s strong BPSW
3.2s extra strong BPSW
for i in [2,4,6,8,10]:
isprime( 10**2000 + 4561 + i )
master: 5.0s
branch: 0.2s
For the Narcissus prime int("1808010808"*1560 + "1"), times are:
6m 2s mr(n, 2)
19m12s is_strong_lucas_prp(n)
13m 9s is_extra_strong_lucas_prp(n)
again noting that gmpy / gmpy2 is not installed, so pow() is quite slow.
If we ran the 46 bases from the old code, we would expect a total isprime
time of about 4.5 hours. If we do a strong BPSW test it is about 25
minutes. Using the "extra strong" test would be about 18 minutes. Adding
another M-R test would add about 6 minutes.
I'll do more tests including with GMPY2 tonight.
--
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.
