Arch Linux

noriko

Member

From: In My Mind

Registered: 2006-06-09

Posts: 535

Website

Re: For those who need a programming challenge

it's done... the python version has been bumped up to r3.4, with the new fix (there was  a bug) for it not outputting correct primes between 79 ad 207;
with this new fix primen+ the c++ implementation can now be bumped to r4.....

i think I've fixed all bugs now, and will be thinking up new improvements  or if u guys have any ideas.. they're welcomed as always...

http://lmu.j2k.cc/primen.py
http://lmu.j2k.cc/primen+

---

The.Revolution.Is.Coming - - To fight, To hunger, To Resist!

Cygnus

Member

Registered: 2006-11-03

Posts: 6

Re: For those who need a programming challenge

Hi all,

I wrote another C++ implementation, which is a little faster.
Here's a benchmark:

D:Documents and SettingsIan ZwaanBureaubladtimer301>timer primeN

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Prime 1000000 = 15485863

Kernel Time  =     0.000 = 00:00:00.000 =   0%
User Time    =    12.562 = 00:00:12.562 = 100%
Process Time =    12.562 = 00:00:12.562 = 100%
Global Time  =    12.562 = 00:00:12.562 = 100%

D:Documents and SettingsIan ZwaanBureaubladtimer301>timer primen+ 1000000 on
ly

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
~~~~~~~~~~~~
PrimeN+ r4
~~~~~~~~~~~~
1000000: 15485863

Kernel Time  =     0.000 = 00:00:00.000 =   0%
User Time    =   184.640 = 00:03:04.640 =  97%
Process Time =   184.640 = 00:03:04.640 =  97%
Global Time  =   189.985 = 00:03:09.985 = 100%

D:Documents and SettingsIan ZwaanBureaubladtimer301>

The source file:
http://ianzwaan.googlepages.com/primeN.zip
Note: make sure that you compile with optimizations enabled (i.e. -O2)

noriko

Member

From: In My Mind

Registered: 2006-06-09

Posts: 535

Website

Re: For those who need a programming challenge

i don't understand what this does....
can u explain a bit more ...
btw, know pretty much nothing about c/c++ so my code may be somewhat , well it may do things that slow it down unnecessarily ...

i just did a comparison,;

compile: g++ -O3 -Wall "prime*.cpp" -o prime*

[root@syztem tmp]# time ./primeN
Prime 1000000 = 15485863

real    0m15.585s
user    0m14.735s
sys     0m0.105s

[root@syztem primen]# ./geany_run_script.sh
~~~~~~~~~~~~
PrimeN+ d4
~~~~~~~~~~~~
1000000: 15485863

real    0m19.327s
user    0m18.564s
sys     0m0.125s

it's hard for me to say anythign about ur code .. it is fast but i don't know what it ...

btw, i did tried passign it a param, 100000; which is what primen was originally optimized for, (seeing how python is slow and that was the test target for primen.py);

might u care to add the optimization for greater numbers ... sqrt(l)*4
[ if u care to help, just add ... q = 4000; after all the check, or remove em if u wish..] ; as was offered by one of the collaborators... on primen.py;

edit; ahaha now i get it ..lol;

btw, y not add const Integer MAX_PRIMES = atoi(argv[1]); instead, so it actually takes the input...

......................................................

:twisted:

---

The.Revolution.Is.Coming - - To fight, To hunger, To Resist!

noriko

Member

From: In My Mind

Registered: 2006-06-09

Posts: 535

Website

Re: For those who need a programming challenge

ok, i did some tests and with a direct comparable code ... ours went 1-2 seconds faster, that's still 3 seconds slower than urs ... so i decided to implement the final bit needed for primen+ r5 ...
now it returns the millionth prime in 8 seconds on a celeron 2.6 ghz, i'm yet to test on anything else ...
i will upload the code soon, when i get my new web server account seupt ...

time primen+ only 1000000
...
1000000: 15485863
real    0m7.905s
user   0m7.448s
sys     0m0.009s

---

The.Revolution.Is.Coming - - To fight, To hunger, To Resist!

Cygnus

Member

Registered: 2006-11-03

Posts: 6

Re: For those who need a programming challenge

time primen+ only 1000000
...
1000000: 15485863
real    0m7.905s
user   0m7.448s
sys     0m0.009s

Wow, that is really fast.

I actually thougt that the 6n+-1 algorithm would be faster than the sieves, but I rewrote my program with the the Sieve of Eratosthenes and it was a lot faster than the 6n+-1 algorithm.

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
PrimeFinder v1.0.0
Prime 1000000 = 15485863.

Kernel Time  =     0.000 = 00:00:00.000 =   0%
User Time    =     1.609 = 00:00:01.609 = 100%
Process Time =     1.609 = 00:00:01.609 = 100%
Global Time  =     1.609 = 00:00:01.609 = 100%

Here is the code:
http://ianzwaan.googlepages.com/primeFinder.tar.gz

btw, the Sieve of Atkin is supposed to be faster than the Sieve of Eratosthenes (with a good implementation).