AutoHotkey Community

It is currently May 27th, 2012, 5:28 am

All times are UTC [ DST ]




Post new topic Reply to topic  [ 12 posts ] 
Author Message
PostPosted: November 18th, 2009, 9:50 pm 
Offline

Joined: July 15th, 2007, 1:43 am
Posts: 1320
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. >_>


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: November 19th, 2009, 5:06 am 
Offline

Joined: December 21st, 2008, 7:29 pm
Posts: 181
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
}


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: November 19th, 2009, 9:25 am 
Offline

Joined: December 17th, 2007, 6:39 pm
Posts: 235
Location: Galati, Romania
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
}


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: November 19th, 2009, 6:26 pm 
Offline

Joined: April 8th, 2009, 8:23 pm
Posts: 3036
Location: Rio de Janeiro - RJ - Brasil
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.
"
Image
Antonio França
My stuff: Google Profile


Report this post
Top
 Profile  
Reply with quote  
PostPosted: November 19th, 2009, 7:49 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
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.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: November 19th, 2009, 7:57 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
MasterFocus wrote:
Yours can be improved
This function returns 1 for 9 or 15.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: November 19th, 2009, 8:15 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
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...


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: November 20th, 2009, 4:17 am 
Offline

Joined: April 8th, 2009, 8:23 pm
Posts: 3036
Location: Rio de Janeiro - RJ - Brasil
@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.
"
Image
Antonio França
My stuff: Google Profile


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: November 20th, 2009, 4:25 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
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.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: February 23rd, 2011, 8:21 pm 
Offline

Joined: April 3rd, 2009, 6:56 pm
Posts: 49
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.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: February 23rd, 2011, 8:50 pm 
Offline

Joined: February 14th, 2005, 4:05 pm
Posts: 4710
Location: Boulder, CO
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.


Report this post
Top
 Profile  
Reply with quote  
 Post subject:
PostPosted: February 23rd, 2011, 9:38 pm 
Offline

Joined: April 3rd, 2009, 6:56 pm
Posts: 49
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.


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: Bing [Bot], Google [Bot], Google Feedfetcher, sks, Stigg and 12 guests


You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group