| View previous topic :: View next topic |
| Author |
Message |
trik
Joined: 15 Jul 2007
Posts: 1320
|
 Posted: Wed Nov 18, 2009 8:50 pm Post subject: IsPrime() - Check if Number is Prime |
 |
|
After looking through the forum, and spending several minutes waiting for benchmarks to finish, I have concluded that this is the fastest prime number verifier (Finishing 1,000,000 iterations in which different integers were used in 3,588 MS on my computer) made in AutoHotkey.
| Code: | IsPrime(x) {
Return x == 2 || x == 3 || x == 5 || x == 7 || (Mod(x, 2) > 0 && Mod(x, 3) > 0 && Mod(x, 5) > 0 && Mod(x, 7) > 0)
} |
It is based off Sieve of Eratosthenes, which is a mathematical algorithm used for generating prime numbers. If anyone has any ideas on how to make the function faster or knows of one that is faster, please do post.
_________________
Religion is false. >_> |
|
| Back to top |
|
 |
entropic
Joined: 21 Dec 2008
Posts: 181
|
| Posted: Thu Nov 19, 2009 4:06 am Post subject: |
|
|
The Sieve of Eratosthenes (O(N)) is better when you need all the primes up to a limit, the Sieve of Atkin (O(N/log log N) does the same thing but faster.
The Miller-Rabin primality test is a fast way to check if a number is likely not composite and it gets more accurate with more iterations.
I noticed while playing around with this it sometimes reports composite numbers as prime.
121, 143, 169, 181, 187
Here's an AHK solution from RosettaCode
| Code: |
MsgBox % IsPrime(1995937)
Loop
MsgBox % A_Index-3 . " is " . (IsPrime(A_Index-3) ? "" : "not ") . "prime."
IsPrime(n,k=2) { ; testing primality with trial divisors not multiple of 2,3,5, up to sqrt(n)
d := k+(k<7 ? 1+(k>2) : SubStr("6-----4---2-4---2-4---6-----2",Mod(k,30),1))
Return n < 3 ? n>1 : Mod(n,k) ? (d*d <= n ? IsPrime(n,d) : 1) : 0
}
|
|
|
| Back to top |
|
|
Petru
Joined: 17 Dec 2007
Posts: 235
Location: Galati, Romania
|
| Posted: Thu Nov 19, 2009 8:25 am Post subject: |
|
|
I like my version...
| Code: | Prim(a)
{
local Prim
ok:=1
Prim:=round(a/2)+1
loop
{
prim--
if prim=1
break
if mod(a,prim)=0
ok:=0
}
if ok
return 1
} |
|
|
| Back to top |
|
|
MasterFocus
Joined: 08 Apr 2009
Posts: 3035
Location: Rio de Janeiro - RJ - Brasil
|
| Posted: Thu Nov 19, 2009 5:26 pm Post subject: |
|
|
| Petru wrote: | | I like my version... |
Yours can be improved:
| Code: | Prim(a)
{
prim := round( a / 2 ) + ( ok := 1 )
while ( prim > 2 )
prim-- , ok := mod( a , prim )
return ok
} |
_________________
"Read the manual. Read it again. Search the forum.
Try something before asking. Show what you've tried."
Antonio França
My stuff: Google Profile |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4710
Location: Boulder, CO
|
| Posted: Thu Nov 19, 2009 6:49 pm Post subject: Re: IsPrime() - Check if Number is Prime |
|
|
| Trikster wrote: | | this is the fastest prime number verifier |
Not really: it finds numbers, which are not multiples of small primes. E.g. 121 = 11*11, but your IsPrime function finds it prime. |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4710
Location: Boulder, CO
|
| Posted: Thu Nov 19, 2009 6:57 pm Post subject: |
|
|
| MasterFocus wrote: | | Yours can be improved |
This function returns 1 for 9 or 15. |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4710
Location: Boulder, CO
|
| Posted: Thu Nov 19, 2009 7:15 pm Post subject: |
|
|
| Petru wrote: | | I like my version... |
It can be simplified a bit, and sped up: it is enough to try potential divisors only up to Sqrt(a): | Code: | Prim(a) {
Loop % Floor(Sqrt(a))-1 {
If !Mod(a,A_Index+1)
Return 0
}
Return 1
} |
However, my function (posted to RosettaCode) performs 15/4 = 3.75 times fewer iterations: you don't have to try even divisors (except 2), divisors of proper multiples of 3 or 5, etc. The actual speed relations depend on the AHK version and CPU type. Most likely the above simple loop is faster... |
|
| Back to top |
|
|
MasterFocus
Joined: 08 Apr 2009
Posts: 3035
Location: Rio de Janeiro - RJ - Brasil
|
| Posted: Fri Nov 20, 2009 3:17 am Post subject: |
|
|
@Laszlo
Thanks for pointing that out. I tested it but probably didn't notice.
Code posted to RosettaCode is yours? Well, thank you, it's pretty fast.
_________________
"Read the manual. Read it again. Search the forum.
Try something before asking. Show what you've tried."
Antonio França
My stuff: Google Profile |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4710
Location: Boulder, CO
|
| Posted: Fri Nov 20, 2009 3:25 pm Post subject: |
|
|
Yes, someone posted my AHK function to RosettaCode. It is not meant to be fast (it uses slow recursive calls), but illustrative to sieving (by 2, 3 and 5) and reasonably short.
I've posted machine code prime testing functions to the forum, which are orders of magnitude faster than pure AHK scripts, and also scripts for the Miller-Rabin primality test, which is even faster for large input. |
|
| Back to top |
|
|
fuzz54
Joined: 03 Apr 2009
Posts: 49
|
| Posted: Wed Feb 23, 2011 7:21 pm Post subject: |
|
|
| Laszlo wrote: | | Petru wrote: | | I like my version... |
It can be simplified a bit, and sped up: it is enough to try potential divisors only up to Sqrt(a): | Code: | Prim(a) {
Loop % Floor(Sqrt(a))-1 {
If !Mod(a,A_Index+1)
Return 0
}
Return 1
} |
However, my function (posted to RosettaCode) performs 15/4 = 3.75 times fewer iterations: you don't have to try even divisors (except 2), divisors of proper multiples of 3 or 5, etc. The actual speed relations depend on the AHK version and CPU type. Most likely the above simple loop is faster... |
I'm guessing you are already aware of this, but this could be even faster by making sure "a" is of the form 6N+/-1 since that is the distribution of possible primes for all N. That doesn't change your function at all, but would matter if generating a list of all primes below a certain number. |
|
| Back to top |
|
|
Laszlo
Joined: 14 Feb 2005
Posts: 4710
Location: Boulder, CO
|
| Posted: Wed Feb 23, 2011 7:50 pm Post subject: |
|
|
| You can use the two possible mod 6 candidates (33.3% of all integers), or the 8 possible mod 30 candidates (8/30 ~ 26.7% of all integers), and so on. For short numbers (up to 64 bits) cleverly generating the next divisor candidate is more costly than blindly trying the next odd number (50%), so the simple loop is faster in most cases. For long integers it is different, but there you should use something like the much faster Miller-Rabin tests. |
|
| Back to top |
|
|
fuzz54
Joined: 03 Apr 2009
Posts: 49
|
| Posted: Wed Feb 23, 2011 8:38 pm Post subject: |
|
|
| Laszlo wrote: | | You can use the two possible mod 6 candidates (33.3% of all integers), or the 8 possible mod 30 candidates (8/30 ~ 26.7% of all integers), and so on. For short numbers (up to 64 bits) cleverly generating the next divisor candidate is more costly than blindly trying the next odd number (50%), so the simple loop is faster in most cases. For long integers it is different, but there you should use something like the much faster Miller-Rabin tests. |
Ahhh, so you are just as fascinated by primes as me. Good stuff. |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Register
Profile
Log in to check your private messages
Log in
