Prime Factor Coding Challenge

[altenbach]

---

@shoneill wrote:
However, yoru comment that you've shaved 50% of your time quite simply frightens me. 

---

Shane,

Well, not quite. 😉 I shaved "nearly" 50% off the prime table generation and only a few % on the factor search. Sorry for the wrong wording above.

First run went from 32 to 22 seconds. Second runs from 9.8 to 9.3 second. So, yes, the overall improvement is not that great!

We are very similar in times: If I simply divide my two first runs, the new time is 0.71 times the old time, which brings me down to about estimated 10.5 seconds on Bruce's rig. OTOH, first run is about 2.37x later runs which is about 12.5 seconds with the above numbers and you win. 🙂

No matter what, we're probably within less than 10% of each other. 😮

I submitted my new version to Bruce for testing. 😉

[BruceAmmons]

Well, Christian is in the lead now.  His new times are 10329 and 5162.

Bruce

[shoneill]

Grrrr, there goes my weekend....... 😄

Well, I'm away this weekend, but in any case....

The problem with interesting coding challenges is the moment where you're trying to get to sleep at night and the questions like "But maybe a Boolean index would be better...." keep coming.  😞

Shane

PS. The difference is now 12%

Message Edited by shoneill on 09-28-2005 08:02 AM

[shoneill]

He he,

Just shaved 17.5% off my prime number generation time.  Technically, this could give me the lead again, but I'll wait for a while before posting.  There's more to come I believe.

:D 😄 😄

Shane.

[altenbach]

---

@shoneill wrote:
Just shaved 17.5% off my prime number generation time. 

---

Shane, you're really starting to breathe down my neck here, I was only able to squeeze another 5% improvement out of my prime generator 😄

[shoneill]

Hmm, yes, but theoretically, that would put you in front again.  After re-running my code, I have been unable to repeat the 17.5% improvement.  I'm stuck at 14%.  I've also found some really wierd behaviour where having a case statement around an array operation speeds things up.  Even when the case statement is hard-wired to TRUE.  This makes a difference of 10% in my code!

Er, maybe I shouldn't be telling you this. 😉

Sooo, anyway..... your existing 12% lead + 5% beats my 14%.  😞

BUT, I have a couple of ideas (sadly enough, they occurred to me as I was falling asleep last night) which should give in the region of 10% increase in speed.

Probably won't have code until next week though.

Shane

[altenbach]

Don't forget, a 5% increase in prime factor generation does not translate into an overal 5% speedup for the first run.

With your numbers (11593, 5459), it means that the table generations takes 6134ms. 17.5% faster would be 5060ms for an overall 10520 on the first run. This is only 10% better. 😉

Is your quoted 14% an overal time or a "prime time"? 😄

So far I stayed away from "Vodoo" code (extra case structures and such). While edting a VI there will always be tiny speed variations and they may disappear when the VI is saved and re-opened. Sometimes things get a bit faster after rebooting the computer (memory fragmentation?).

Shane, may I ask what the file size is of your VI? Mine is only around 80kB.

[Chaos]

Since my question is somewhat related figured I would stick my nose in here for a second.  While I am not really interested in competing in the competition I do find it very interesting.  For fun the last week I have been brainstorming and looking for better methods of generating prime numbers.  After much fiddling around with my code I came up with, I believe, an interesting way to generate them.  While I am still looking for improvements in the design, I would much like to see some benchmarks just on the prime generation side of things.  Could someone post some timing numbers just for my reference?  I can work with either timings for generating primes up to number X or timings for X numbers of primes.

Obviously, since theres a competition going on revolving around this topic, I will choose not to post any of my code or opinions until it is over.  At which time I would like to spark a new thread to see if what I am doing is logistically sound or not...

If you could help out with the timings would be nice to place the ranges in the millions.  I still have some verifications to do and a couple more improvement avenues I am following but on my 333MHz machine at home I can generate all primes up to 2.4 million in less than a couple of seconds if that.

Thanks!

[altenbach]

Hi Chaos,

It was nice meeting you at NI week. 🙂

From the timing behavior in my code, you can tell that I generate all possible prime numbers in advance. On Bruce's test rig, the first run takes 10329ms and the later runs take 5162ms. From the difference, we can tell that the time to create the list of prime numbers takes about 5 seconds (the difference between the two numbers).

Since we are dealing with inputs of 16 decimal digits, we need to create a cache of all possible prime numbers up to 8 decimal digits (99999999), or about 100 millions. 😮

The above numbers are for Bruce's machine. On my 1GHz PIII the prime generation takes about 12 seconds and scaling to 333MHz, you should be able to generate all primes up to 100 millions in well under 40 seconds on your rig to be comparable (guessing wildely ;)). I would think that a ceiling of 2.4 million would be significantly faster. :).

[Chaos]

Thanks for the timings Altenbach!

It was nice to meet you also.  I'll look forward to seeing you again next year i'm sure.  I will see how my algo does against 99999999.  Using those three different comparisons I should be able to at least get an idea of how efficient I made it so far...