LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Prime Factor Coding Challenge

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.
Using LV 6.1 and 8.2.1 on W2k (SP4) and WXP (SP2)
0 Kudos
Message 21 of 186
(2,704 Views)
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! 🐵
0 Kudos
Message 22 of 186
(2,626 Views)

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

Bruce Ammons
Ammons Engineering
0 Kudos
Message 23 of 186
(2,703 Views)
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.
Using LV 6.1 and 8.2.1 on W2k (SP4) and WXP (SP2)
0 Kudos
Message 24 of 186
(2,639 Views)
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.


Using LV 6.1 and 8.2.1 on W2k (SP4) and WXP (SP2)
0 Kudos
Message 25 of 186
(2,598 Views)

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

Bruce Ammons
Ammons Engineering
0 Kudos
Message 26 of 186
(2,585 Views)
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
0 Kudos
Message 27 of 186
(2,554 Views)

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

0 Kudos
Message 28 of 186
(2,557 Views)
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
Bruce Ammons
Ammons Engineering
Message 29 of 186
(2,553 Views)
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.....
Using LV 6.1 and 8.2.1 on W2k (SP4) and WXP (SP2)
0 Kudos
Message 30 of 186
(2,540 Views)