Friday, March 9, 2012

Sieve of Eratosthenes revisited

I recently revisited this after it coming up last year when my nephew was playing around with primes. This time I decided to implement a basic bit-array myself in c. Without the overhead of calls to the boost dynamic bitset in c++ the runtime dropped even more.




Back when I had initially run the c++ version this was the output for 40 billion:

snits@perelman:~/proj/cpp=>time ./se 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 90m48.631s
user 90m40.850s
sys 0m3.589s

Here is the output for running the c version with my own bitarray:

On my i7 system:

snits@cantor:~/proj/c=>time ./sieve 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 16m49.468s
user 16m23.482s
sys 0m6.471s


On my q6600 system:


snits@perelman:~/proj/c=>time ./sieve 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 24m57.106s
user 24m47.370s
sys 0m2.562s

That is a nice gain due to removing the overhead of calls to the dynamic bitset class in C++.

No comments:

Post a Comment