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?

[curaga]

My algo is faster :P

time ./primes
The 1000000th prime is 15485863

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

[nes1983]

System profiler says:

Processor Name: Intel Core 2 Duo
Processor Speed: 3,06 GHz
Number Of Processors: 1
Total Number Of Cores: 2
L2 Cache: 6 MB
Memory: 4 GB
Bus Speed: 1,07 GHz

And GCC:

$ gcc --version
i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5646) (dot 1)
Copyright (C) 2007 Free Software Foundation, Inc.

[howlingmadhowie]

With this code will my system works fast?

No no, it's just to check how fast your computer is.

More specifically the thing that takes the time here is the line

if(totest%primes[i]==0) return 0;

because calculating the remainder of a division takes a long time. I'm using an AMD phenom chip and it seems to have a pretty good implementation of this, but Intel looks to be a bit better.

Using fairly standard hardware you could find the remainder of dividing two 32-bit words in 32 operations. sparc architecture has an operating called mulscc to do something similar for multiplication, but it didn't used to have something similar for division. maybe they added something at some stage. if i have time today i'll write a blog post about how mulscc and divscc (i suppose it would be called that) work.

with modern intel and AMD chips everything just gets exported to the maths co-processor and no one knows how that works.

[Avenger]

something looks wrong, but this is my output:

[avenger@avenger3 tmp]$ gcc prime.c
.&[avenger@avenger3 tmp]$ time ./a.out

real 0m0.004s
user 0m0.000s
sys 0m0.000s
[avenger@avenger3 tmp]$ gcc --version
gcc (GCC) 4.4.3
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

on a:
AMD Athlon(tm) 64 Processor 3000+ @*2.00ghz

I just copied and pasted the code from this site