how fast is your computer?

[howlingmadhowie]

here's a simple C program i just wrote to find the nth prime number.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long *primes;
int numfound;

int isprime(long totest) { 
  int i=0;
  for(i=0; primes[i]*primes[i]<=totest; i++) {
    if(totest%primes[i]==0) return 0;
    if(i>=numfound) return 1;
  }
  return 1;
}

int main(int argc, char** argv) {
  int tofind;
  long totest;
  time_t start, end;

  if(argc!=2) exit(EXIT_FAILURE);
  tofind=atoi(argv[1]);

  numfound=1;
  primes=malloc(sizeof(long));
  primes[0]=2;
  totest=2;

  start=clock();
  while(numfound<tofind) {
    totest++;
    if(isprime(totest)) {
      numfound++;
      primes=realloc(primes, numfound*sizeof(long));
      primes[numfound-1]=totest;
    }
  }
  end=clock();

  printf("prime number %d: %ld\n", numfound, totest);
  printf("total time: %.2f\n\n", (end-start)/(float)CLOCKS_PER_SEC);
  free(primes);
  return EXIT_SUCCESS;
}

On my computer it's this fast:

╭─[/data/software/c]─[howie@howie-desktop]─[0]─[111]
╰─[:)] % ./primefinder 1000000
prime number 1000000: 15485863
total time: 7.65

This is my computer btw:

╭─[/data/software/c]─[howie@howie-desktop]─[0]─[112]
╰─[:)] % cat /proc/cpuinfo | grep -m1 "model name"
model name      : AMD Phenom(tm) II X4 965 Processor

How fast is your computer?

[rohcQaH]

primes=realloc(primes, numfound*sizeof(long));

How nice, a single-threaded benchmark of libc's memory management!

if only there was a way to know the number of primes you're going to store in advance...

[howlingmadhowie]

How nice, a single-threaded benchmark of libc's memory management!

if only there was a way to know the number of primes you're going to store in advance...

it's actually barely faster (7.62s on my system) if you malloc the whole space in advance. i'd gestimate that about 99% of the time is spent calculating the modulus.

[rohcQaH]

anyway, I beat ya using a slightly more clever implementation

~> time (wget -q -O - http://www.wolframalpha.com/input/?i=prime%5B1000000%5D | grep 'Result' | sed -e 's/^.*alt="\([0-9]*\)".*$/\1/i')
15485863

real 0m1.814s

[nes1983]

nikos-mbp-3:edprime niko$ gcc -Wall -std=c99 -O3 ed.c -o ed
nikos-mbp-3:edprime niko$ ./ed 1000000
prime number 1000000: 15485863
total time: 6.58

[howlingmadhowie]

nikos-mbp-3:edprime niko$ gcc -Wall -std=c99 -O3 ed.c -o ed
nikos-mbp-3:edprime niko$ ./ed 1000000
prime number 1000000: 15485863
total time: 6.58

what's your cpu, niko? and what version of gcc are you using?

[Shining Arcanine]

it's actually barely faster (7.62s on my system) if you malloc the whole space in advance. i'd gestimate that about 99% of the time is spent calculating the modulus.

Here is a patch that does that:

--- t.old       2010-03-06 23:38:48.579241698 -0500
+++ t.c 2010-03-06 23:37:39.074240092 -0500
@@ -23,7 +23,7 @@
   tofind=atoi(argv[1]);
 
   numfound=1;
-  primes=malloc(sizeof(long));
+  primes=malloc(sizeof(long)*totest);
   primes[0]=2;
   totest=2;
                                                                                       
@@ -32,7 +32,6 @@                                                                      
     totest++;                                                                         
     if(isprime(totest)) {                                                             
       numfound++;                                                                     
-      primes=realloc(primes, numfound*sizeof(long));                                  
       primes[numfound-1]=totest;                                                      
     }                                                                                 
   }

You are right that all of the time is spent in the modulus. When I wrote my program 2.5 years ago, I went with the erathothenes sieve algorithm because it did not require that I calculate the moduli, which was a huge performance boost. It is possible to calculate the moduli using a square and multiple approach, but doing it efficiently would require O(m*n) auxillary memory and some dynamic programming, but I doubt that it would beat the erathothenes sieve.

[BlackStar]

Every time I see algorithms like this implemented in C, I weep. Use something functional, save a few electrons.

Also, Euler's Sieve FTW.

Edit: Prime95 is a much better benchmark.

[DuSTman]

dustman@ixeron ~/primetest $ gcc -p primetest.c -o primetest -O3
dustman@ixeron ~/primetest $ ./primetest 1000000
prime number 1000000: 15485863
total time: 5.72

[curaga]

My algo is faster :P

time ./primes
The 1000000th prime is 15485863

real 0m6.256s
user 0m6.244s
sys 0m0.007s