1. Junior Member
Join Date
Nov 2007
Posts
11

## how fast is your computer?

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

Code:
```#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:

Code:
```╭─[/data/software/c]─[howie@howie-desktop]─[0]─[111]
╰─[:)] % ./primefinder 1000000
prime number 1000000: 15485863
total time: 7.65```
This is my computer btw:

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

2. Senior Member
Join Date
Nov 2008
Posts
801
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...

3. Junior Member
Join Date
Nov 2007
Posts
11
Originally Posted by rohcQaH
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.

4. Senior Member
Join Date
Nov 2008
Posts
801
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

5. Junior Member
Join Date
Jan 2010
Posts
2

## Niko's result

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

6. Junior Member
Join Date
Nov 2007
Posts
11
Originally Posted by 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
what's your cpu, niko? and what version of gcc are you using?

7. Senior Member
Join Date
Feb 2008
Location
Linuxland
Posts
5,705
My algo is faster :P

time ./primes
The 1000000th prime is 15485863

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

8. Junior Member
Join Date
Jan 2010
Posts
2

## my machine

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.

9. Junior Member
Join Date
Nov 2007
Posts
11
Originally Posted by debrah.h48
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
Code:
`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.

10. Junior Member
Join Date
Dec 2007
Posts
13
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