Prime Factor Coding Challenge

[shoneill]

Thanks Bruce,

erm, I hadn't even read that page before.  Now I know a bit more about the challenge.

Is the test array always going to be of increasing difficulty?  With only the last number requiring two 8-digit primes?

Ciao

Shane.

[altenbach]

Jurgen 313,

Would you mind setting your y-axis to logarithmic mapping? It would be interesting to see some details below N=70. 😉

(Of course maybe you want to keep this secret. I wonder ho much somebody can tell about the algorithm just by looking at that curve shape! 🐵

[BruceAmmons]

Shane,

Take a look at the test vi I posted.  It has a sample list of 100 numbers of increasing difficulty.  It should give you a very good idea of what the final list will be like, because I will use the exact same program to generate a new list for the final test.

Bruce

[shoneill]

Thanks again Bruce,

I've downlaoded the VI already.  It's nice for everyone to have the same test VI so that preliminary results are more comparable.

Shane.

[shoneill]

OK, I'm going to tempt fate and publish some results so far.

I've also implemented a "brute force" test, but I've included quite a few tricks up to now.  I suppose it's not really "brute force" any more.

I generate all of my prime numbers from scratch except 2, 3 and 5 and can finish the test with the 100 numbers provided by Bruce without any errors.

I'm running the tests on a P4 2.8GHz with HT enabled and 1Gig of RAM.

My first run takes a total of 8.914 seconds (including prime number generation), whereas each subsequent run takes 3.802 seconds.  See the attached screen shot.

I know there's still some room for improvement, especially with the prime number generation.

Shane.

[BruceAmmons]

Shane,

Go ahead and send me your vi, and I will do a time test on my computer.  I already have tested Christian's, and after I have three I will start posting the top times on my machine.  This will give everybody a uniform comparison of their results.

Bruce

[ohw313]

Okay,

OKay, have not had much time, but have managed to make big improvements.

Have included my latest run(From scrath) = 31 sec (Yes, very sad compared to Shane).

Mine does do the first 70 in 1 sec. (However the method fades badly in the higher up).

Once I get a little time I will attack again.

Good Luck

Jurgen

[altenbach]

Shane,

We seems to program along the same lines 😉 My latest results show almost the same pattern.

I tuned a few things and was able to squeze another ~50% off my time (not yet submitted to bruce). Here's the latest, still on my ancient 1GHz PIII 512MB Laptop.

On an 1.8GHz Athlon XP 2500 1GB, the times are 9/3.5 seconds (first run/later runs) and on an 2.2GHz Dual CPU/Dual Core (=4xCores)  Athlon 4GB 6/2.6 seconds (there is nothing optimized for paralell execution, so it probably mostly utilizes only one core). In my experience from earlier challenges, Athlons do better on these kind of computations than Intel machines on a per GHz basis, so it is possible that we are extremely similar. Only Bruce will be able to tell.

It might be intersting to develop an algoritm optimized for multiple processors. I could test them on the above dual/dual screamer for extra credit after the competition 😉

There is still some slack left in the code, maybe I'll look into it in a week or so.

Message Edited by altenbach on 09-27-2005 09:24 AM

[BruceAmmons]

Well, I have three submissions, so here are the current standings:

Shane O'Neill            11593, 5459

Christian Altenbach   14777, 5260

Dan Bookwalter         86371

These are first and second run times.  Of course, only the first run counts.

Submit your entry to get on the list!!!  If you don't make the list, I will let you know what your time was via email.

It looks like Christian might move to the top of the list if he sends me his latest version.

Bruce

[shoneill]

Christian,

Indeed, the two sets of data look remarkably similar.  I wouldn't be surprised if many of my "tricks" were already in your code (and viseversa).

However, yoru comment that you've shaved 50% of your time quite simply frightens me.  Aaah!  I did say I was tempting fate when I posted my results 😉  By the way, have you shaved 50% off the first run, the second run or all of them.  Hey, while you're at it, why not just post the code....... 😄

Hmmm, I reckon there's still plenty of steam left in the "brute force with tricks" approach yet.

Shane.

PS Thanks for the interim results Bruce.  Good to have results from the same machine.  It''s also good to know that only the first run counts.....