20070718, 05:59  #1 
Jul 2007
17 Posts 
Small prime test divisor efficiency strategy
I'm coding my own c++ library of number theory routines (because it's the best way to learn!).
I am now working on a general "is this number prime?" routine. My basic strategy is trial division for the first (few hundred?) primes, then apseudoprime tests for a=2,3,5, etc. If I get really ambitous I'll implement the BalliePSW test. My question is a general efficiency one. For testing the list of the first few hundred primes, is it generally faster to do trial divisions of each divisor sequentially, or to do a GCD with the product of many primes at once? I am sure the exact balance depends on implementation efficiency of divides and GCD, but I would expect that for testing hundreds of divisors, you'd end up using the GCD to do many in parallel. But online code (for example the clean presentation by Thomas Nicely) uses explicit division for each of the the first 6000+ primes, not GCD. I have only penciled in the rough guess of computational efficiency but surely a GCD of many primes at once will take far fewer operations (admittedly using larger numbers) than explicit divides. Or maybe the "early abort" of individual tests is efficient.. once you find a divisor, you don't really care about any others, you know it's not prime. Thanks for any advice! 
20070718, 13:10  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,889 Posts 
Quote:
A GCD of (N, Prod p_i, i < k) should be faster than trial dividing the primes up to p_k, but (as you point out), whether it is faster in practice depends on HOW LIKELY it is that N is prime. Trial division aborts after a divisor is found, so you may not do most of the divisions. If N is drawn truly uniformly at random from some interval, then trial division should be faster on average. If you have some prior expectation that N might be prime (for whatever reason), the GCD's will probably be faster. However, you are optimizing something that only takes microseconds anyway. 

20070718, 16:36  #3  
Jul 2007
17 Posts 
Quote:
You're also right that actual evaluation is microseconds, but in my mind this may be something that could be repeated bilions or trillions of times, so it's elegant to get it efficient. [That kind of elegant optimization is the bane, and the joy, of perfectionist programmers.] Thanks! 

20070718, 17:03  #4  
"Bob Silverman"
Nov 2003
North of Boston
1D84_{16} Posts 
Quote:
by trial division? 

20070718, 18:18  #5  
Jul 2007
17 Posts 
Quote:
That.... is a very very good question... and one that I hadn't clearly thought about! I am so "new" to the game I am just building up some fundamental routines and hadn't thought how they might be used. The only answer to a billionsofisPrime tests is probably some naive algorithm such as doing trial divisions for (lots) of small primes, and the routine would use the prime test to come up with those trial divisors. But that's a pretty inelegant algorithm.. it'd be fine for hundreds or even a million imes, but a billion.. ? Heh, thanks for making me think about the importance of what routines need speed and which don't. Your simple reply made me think about that more. 

20070718, 18:39  #6 
"Ben"
Feb 2007
111010110100_{2} Posts 
If you are new, and looking for routines/algorithms to learn about and implement, one that is relevant to finding primes in a (possibly very large) list of numbers is a sieve.
The sieve of Eratosthenes is simple, and quite well known. However, really efficient versions involve some sophisticated coding, knowledge of the computer architecture, and some number theory to boot. It is a great algorithm for people that like to tinker/optimize. Here are a couple good sites that descibe efficient versions of the algorithm. http://www.ieeta.pt/~tos/software/prime_sieve.html http://wwwhomes.unibielefeld.de/achim/prime_sieve.html  ben. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Probability that N is prime given each divisor of N has the form 2*k*p+1  carpetpool  Miscellaneous Math  6  20170901 13:59 
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve  mickfrancis  Factoring  2  20160506 08:13 
blend / small FFT torture test on linux ?  lukasz  Linux  1  20070109 16:16 
Question of efficiency: Test VS Generator  synergy  Miscellaneous Math  13  20041014 18:14 
Search for a number theoretic function related to "prime divisor sums"  juergen  Math  2  20040710 23:01 