Is n prime?

While I was finding the right path to travel with my assignment, I figured out a fairly efficient method of calculating whether n is prime or not:
unsigned int
prime(unsigned it ofn) {
        /\*
         \* :: returns 1 if ofn is prime, 0 otherwise
         \*
         \* precondition: ofn > 0
         \*/

         unsigned int root; /\* |_sqrt(ofn)_| \*/
         unsigned int count;
         unsigned int mark = 1; /\* our boundary condition var \*/

         /\* we only need to go to floor(sqrt(ofn)) \*/
         root = (unsigned int)floor(sqrt(ofn));

         for (count = 2; count <= root; count++) {
                 if (!(ofn % count)) {
                         /\* not prime, so escape out \*/
                         mark--;
                         break;
                 }
         }
         return (mark);
}
How much more efficient could I get with this routine?
Comments:

This is an old chestnut, going back to the ancient Greeks. Google on "Eratosthenes sieve".

do 2 as a special case then start the loop at 3 and increment by 2. Saves half the divisions.

next, do 2 and 3 as special cases. start the loop at 5 and increment by 6. test only count and count+2 in the loop, since count+1, count+3, count+4 and count+5 are all divisible by 2 or 3 (proof left to reader.) Now you're only testing 1/3 of the divisors, and you've "unrolled" the loop so the loop overhead is amortized over two checks instead of just one.

technique can be extended but with rapidly diminishing returns (next step is to increment by 30 and test only 8 of the 30 numbers in each increment -- that only drops from .333 to .266)

further speedups possible but require some fairly exotic number theory results

Posted by Rich McAllister on April 05, 2005 at 04:05 AM EST #

Thanks Rich --- yes, I'd forgotten about the old sieve. It's been a long time since I did anything serious with numeric algorithms. One thing that this whole exercise has taught me is that people in Sun a really, really keen to engage in intellectual jousting like this. I love it and would not give it up for anything.

Posted by James McPherson on April 05, 2005 at 04:32 AM EST #

James,

Nice write up, it will be good to know as a software release engineer as well... time to review the makefiles that I maintain. Also, do you have any thoughts on why java would be running slower on sparc/solaris vs. opteron/solaris or xeon/linux? I have a simple sorting program that is whicked fast on the amd box we have and burries the sparc box I was running on.

dl

Posted by Dan Lacher on April 05, 2005 at 03:13 PM EST #

After reading your comment on algorithms I couldn't help but respond to this. The fantastic book, "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein outlines the Miller-Rabin primality test, also explained here. I won't try and explain it here (wikipedia does a good job) but it's pretty efficient, being a polynomial time algorithm. You could also implement FFT if you like for extra geek points!

Posted by Ben Cooper on April 07, 2005 at 04:47 PM EST #

Post a Comment:
Comments are closed for this entry.
About

I work at Oracle in the Solaris group. The opinions expressed here are entirely my own, and neither Oracle nor any other party necessarily agrees with them.

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today