Comment #50 on issue 3809 by cas...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Dana,
I've updated is_extra_strong_lucas(). Can you test r816?
Thanks, Case
--
You received this message because this project is configured to send all
issue
Comment #47 on issue 3809 by cas...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Dana,
I've committed another set of fixes. Can you give r814 a try?
Case
--
You received this message because this project is configured to send all
issue notifications
Comment #43 on issue 3809 by dana.jac...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Case,
Yes, the dev version works (and does the strong test, yay). Trying to
verify with Feistma's database, I found this segfaults:
Comment #44 on issue 3809 by cas...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Dana,
I took a quick look before I had to leave for work and I think I spotted
the cause of the segmentation fault. I'll try to fix it this evening.
Case
--
You
Comment #45 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Do a pull request as soon as you have code. That's the easiest way to even
see what you have done, not to mention comment on it.
--
You received this message because
Comment #46 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Apparently I can make a pull request for you.
https://github.com/sympy/sympy/pull/2209.
--
You received this message because this project is configured to send all
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
Comment #42 on issue 3809 by cas...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I thought I had fixed is_bpsw_prp() and is_strong_bpsw_prp() in gmpy2
2.0.0. :(
I committed a fix to the svn repository (r813). Can you give that a try?
There is a
Comment #37 on issue 3809 by dana.jac...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I've been working on primality tests and proofs for a Perl module, so this
is something I've been looking at a lot recently. Here are my long-winded
thoughts, with
Comment #38 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Thanks for the write up. I didn't realize that gmpy2 has this
functionality. We already support gmpy and gmpy2 as optional dependencies
to make the polys faster. We
Comment #39 on issue 3809 by dana.jac...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I can check the gmpy2 functions -- the underlying code should be solid
since it was written for a PRIMO validator that has been used a lot in the
last two years,
Comment #35 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
See http://www.trnicely.net/misc/bpsw.html for discussion about a test that
combines Miller-Rabil with Lucas-Lehmer.
--
You received this message because this project is
Comment #36 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
See http://www.trnicely.net/misc/bpsw.html for discussion about a test that
combines a single Miller-Rabin tests with the Lucas-Lehmer test.
--
You received this message
Updates:
Labels: -NeedsReview -smichr
Comment #34 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
that PR has been committed but I'll leave the issue open. Although maybe
there is a different algorithm that might be faster,
Comment #28 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
the b**2 % 2 thing actually doesn't matter. b is already reduced mod n
from the previous line
Yeah, but n is huge in the case of the narcissus prime...so it can matter.
Comment #29 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
The code referred to online that is 2X faster is only using 20 bases (vs
46) to make the determination of primality so I think that explains why it
is faster.
--
You
Comment #30 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
On the basis of comment #13 I think this issue should be closed as invalid.
A 3200 digit number takes 65 seconds to square mod n. There is no way the
isprime test is
Updates:
Labels: NeedsReview smichr
Comment #31 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
https://github.com/sympy/sympy/pull/2119
--
You received this message because this project is configured to send all
issue
Comment #32 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
@asmeurer: Sorry, I misunderstood your question. And I have run the test on
the narcissus prime. It's been running for a couple of hours now but I am
only using a
Comment #33 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Oh I see that both of those inefficiencies have been fixed in the PR by
Chris.
--
You received this message because this project is configured to send all
issue
Comment #18 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
See the tests above...a 262k digit base being squared either takes
about .002 seconds with pow or 10,000x longer with **
--
You received this message because this
Comment #19 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Oh of course. It will indeed be much faster with pow because it computes
the mod before squaring.
But is that the source of the slowdown here?
--
You received this
Comment #20 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Well, I suppose we can just test out with large primes (Mersenne primes
maybe) for that. As I wrote before, on my workstation, it took the same
time with either
Comment #21 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Btw, I ran a python script that uses the MR algorithm (found here :
Comment #22 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Do primes represent the worst case scenario in this algorithm. Should we
also test against composites?
--
You received this message because this project is configured
Comment #23 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Well, AFAIK, for the cases in the _mr_safe function (that is for if n
1), we can just test for certain primes and know _for sure_
whether n is
Comment #24 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
And just to be clear, we don't need to test against composites *also*.
Primes themselves are good enough.
We are using any numbers between 2 and n-2 as witnesses to
Comment #25 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
You misunderstood my question. I'm not talking about the witnesses. I'm
talking about the inputs to isprime. You keep talking about testing it
against some large
Comment #26 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
By the way, the b**2 % 2 thing actually doesn't matter. b is already
reduced mod n from the previous line, so using pow shouldn't make any
difference, especially since
Comment #27 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Any one care to compare timings for
http://en.literateprograms.org/index.php?title=Special:DownloadCode/Miller-Rabin_primality_test_(Python)oldid=17104)
to SymPy with
Comment #16 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
It's mod n but it's not n**2 it's b**2:
b = (b**2) % n --should be-- b = pow(b, 2, n)
...but it's not going to help much when computing b = pow(base, t, n)
involves
Comment #17 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I think modular exponentiation helps the most with large powers.
--
You received this message because this project is configured to send all
issue notifications to this
Comment #13 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
the mr routine raises the bases to a large power mod n. The larger the
power the longer this takes. Since the number in question here has about
16000 digits we won't
Comment #14 on issue 3809 by smi...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
btw, the difference between n**2 % n and pow(n,2,n) can be pretty dramatic:
p=1
while 1:
... n=int((10**p))
... t=time();j=n**2 % n;print time()-t,p
... p*=2
...
0.0 1
Comment #15 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
It's not mod n. n**2 % n is always 0.
--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust
Comment #5 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Certainly. In any case, I'll try to look for these inefficiencies today and
see what I find.
--
You received this message because this project is configured to send
Comment #6 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
So I looked at the code. The only inefficiency I found was that 2
parameters were being calculated many times in the _test function (line 62
and 63) when they should
Comment #7 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I ran it on my computer and it took several hours to finish.
--
You received this message because this project is configured to send all
issue notifications to this
Comment #8 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
If you have time, maybe run it with line_profiler.
--
You received this message because this project is configured to send all
issue notifications to this address.
You
Comment #9 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I wonder if pow(b, 2, n) would be faster.
--
You received this message because this project is configured to send all
issue notifications to this address.
You may
Comment #10 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
We should add some kind of verbose flag to isprime that gives the status,
similar to factorint.
--
You received this message because this project is configured to send
Comment #11 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
I'm travelling right now and am away from my workstation. I'll see what can
be done once I'm free.
--
You received this message because this project is configured
Comment #12 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
My internet is messed up right now and I don't have the python-dev package
so I cannot build line profiler right now. But using %time on ipython, I
don't think that
Comment #2 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Well, we are using the Rabin-Miller Strong Pseudoprime Test
(http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html) right
now which is probabilistic in
Comment #3 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Scratch the last line.
The user ran Iterative method for Fermat's Test which ran in 18 minutes
on PyPy so perhaps we should implement a deterministic test after all.
Comment #4 on issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
It's also possible that we are doing something inefficiently in Miiller
Rabin.
--
You received this message because this project is configured to send all
issue
Comment #1 on issue 3809 by idlike2d...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Can implementing AKS primality test will be of any help in this issue??
--
You received this message because this project is configured to send all
issue
Status: Valid
Owner:
Labels: Type-Defect Priority-Medium Combinatorics
New issue 3809 by asmeu...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
See http://www.johndcook.com/blog/2013/01/17/narcissus-prime-in-python/.
The code
48 matches
Mail list logo
