Prime Factor Coding Challenge

[BruceAmmons]

Okay, here are the official results:

The official winner is....(drumroll please)....Ben Buhrow.  His submission clocked in at an amazing 86 milliseconds with all of the answers correct.  Along with the official list of 100 numbers, I tested several combinations that can be difficult to solve, such as repeated large roots.  Ben's submission correctly determined the roots in all situations.  This was a very impressive solution.

Second place goes to Franz Ahlers with 112 milliseconds.  His solution solved the list of 100 numbers properly, but failed some of the difficult combinations I tested for robustness.  Franz gets an honorable mention for being the first to submit a solver based on the SQUFOF algorithm.  When his time was an order of magnitude faster than all the previous entries, that really changed the strategy of the challenge.  Franz was also kind enough to explain his strategies, which was an impressive demonstration of friendly competition.  Not many people would explain their solution to the competition.

Third place goes to Shane O'Neill with 9821 milliseconds.  Shane's entry was the fastest entry using the standard trial division algorithm.  His entry was also very robust, passing all the extra tests.

Thanks to all the people that participated in this challenge.  We had a lot of fun and learned a few things along the way.

Bruce

[shoneill]

Wow.  86 millisconds.  Compared to my entry (9821 milliconds) that's a 9821/86 = 115 times speed improvement!  >gulp<

I really did have the feeling that there were more efficient ways to do things than my algorithm, and I found a few in the literature, but never got around to actually implementing them.  But 100 times faster.  That kind of takes my breath away.

Ben Buhrow, I take my hat off to you (To parts of the world where this may not be a commonly used expression, it means he has well earned my respect).

Well, I would if I was wearing a hat, but the sentiment remains.

And to Franz, a mere 88 times faster than me, congratulations also.

This leaves me wondering if there were only two entries which were based on one of the more efficient algorithms?  Personally I had a look at quadratic sieve, SQUFOF and others, but I failed to implement any of them properly (SQUFOF I failed to understand, possible due to time constraints )

I actually got third place?  That's unexpected.  I was expecting Altenbach to beat me.  How about the algorithm using the least amount of memory and the other categories we mentioned earlier?

Finally, to Bruce, a thanks for organising and supervising the challenge.  As I've written during my submission, I've rarely had so much fun, or learned so much (isn't that the same thing?) during a challenge.  I can just feel all of those olf math lectures coming back now.....

Shane.

Message Edited by shoneill on 01-18-2006 08:03 AM

[rolfk]

---

@bsquared wrote:

Altenbach,

thank you for providing that link... i'm pleasantly surprised at how well labview does in computationally intensive tasks according to that chart.  like it says however, every comparison is application (and implementation) specific.

clearly, i am limited by my coding skills, and not any limitations in the language itself.

that said, i'm making progress - my factorizor works now and is pretty fast, but not sub-second yet.

---

LabVIEW is a real compiling language and always has been quite good in the genereated code although with a C compiler and some highly optimized parameter settings you always will be able to get faster code of course.
The problem with LabVIEW is mostly that it is so easy to write inefficient code, since you do not really have to think about how to implement an algorithme in terms of memory allocation and such but instead can just start to code away. When implementing the same algorithme in C you inevidently have to think about memory allocations and intermediate variables and by doing so the step to do optimizations on that level is closer to your thinkings and often also more obvious.
The only area where it is usually hard or impossible to get LabVIEW code that compares well to C code is when you do heavy bit crunching such as in modern compression or encryption algorithmes. As long as the crunching is done on byte level however it is usually possible to come up with an implementation that can compete with non-highly optimized C code although the diagram may sometimes look a little bit less straightforward than what you would think about at first when trying to implement the algorithme.

Rolf Kalbermatter
 

[shoneill]

Rolf,

You have hit on a point I've encountered many times (Especially during coding challenges).

There is often quite a difference between fast-looking and fast-executing code.  When coding, I have to keep telling myself that the amount of space on the screen required to code something is not neccessarily tied to the execution speed (And I mean USED space, not empty space of course).  To my shame, this has often led to some "trial and error" algorithm implementations which, although requiring more code, sometimes run significantly faster.  I personally find even a basic understanding of the actual computational hardware (CPU, RAM, Cache) to be of immense help on this point.  Both my median machine entry and this one used an "optimisation" based on a purely hypothetical case (Parallel operations of arrays being faster than sequential operations).  In both cases, there were clear optimum array sizes, often related to the amount of registers on the CPU, and the size and speed of the processor cache, even though some of my previously-held ideas of how LabVIEW uses this hardware has been proven false.

Having said that, I still find a (perverse?) joy in generating what I would call "elegant" code which is nice neat  code without sacrificing too much execution speed (and preferably small in terms of screen space and required memory).  I know there's at least one 5-star Champion who feels the same, but he's simply better at it than me.  🙂

Sorry for the rant, but I felt what you mentioned in your post was really spot-on.

Shane.

[rolfk]

---

@shoneill wrote:

Having said that, I still find a (perverse?) joy in generating what I would call "elegant" code which is nice neat  code without sacrificing too much execution speed (and preferably small in terms of screen space and required memory).  I know there's at least one 5-star Champion who feels the same, but he's simply better at it than me.  🙂

---

Unless I'm coding a code challange (and I haven't done so in quite some time) I would always go for a clean and compact LabVIEW diagram instead of trying to squezze the last bit of speed performance out of LabVIEW or the system. Of course that doesn't automatically mean that a clean and compact diagram is always slower, quite often clean code and high performance go actually quite well together.

Rolf Kalbermatter

[bsquared]

Thank you for the compliments Shane.  It really means a lot to me, since I spent a lot of time looking up at most of you involved in this competition as previous winners of coding challenges.  And I must stress that the 115x improvement is all due to the algorithm employed, not an overwhelming improvement in coding efficiency.  This is specifically why I didn't even submit a trial division version - I doubted I could compete.

I'll post the solution eventually (unless it will go on the main Labview site ??), but I can say a few words here about what I submitted, for those curious.  The solution actually implemented 5 algorithms.  The Sieve of Erathosthenes, trial division, SQUFOF, Brent's Rho, and Rabin-Miller strong pseudoprime testing.  I used the sieve and trial division to remove small primes from N, before trying Shanks method with several small multipliers.  SQUFOF is a N^(1/4) algorithm, meaning that one could expect to find a solution after N^(1/4) steps.  It is also sensitive to some esoteric properties of the number itself - certain numbers are much easier to factor using this method than others (I still don't understand this completely).  But in an effort to create a number that was easy to factor, I would multiply N by a small multiplier and then abort the algorithm after 3*N^(1/4) iterations and try a different multiplier.  On average, I found (and papers out there back this up) that using multipliers and early aborting will factor N faster than just cranking away with no multiplier.  Still, some pathologic N will fail SQUFOF for all multipliers I was willing to try (prime N included).  Enter Brent.  This method was there mostly for backup, and fortunately was not normally needed as it is quite a bit slower.  But it will almost always find a factor of N for numbers this size.  Rabin-Miller weeded out primes before calling Brent.  I suspect that all these backups is why my solution was able to factor the difficult numbers Bruce threw at it.  But the speed is due to SQUFOF with small multipliers. 

An interesting tweak to this code that might make it even faster would be to race multipliers in parallel loops of SQUFOF.  This would take advantage of any multi-core processors as well as maybe optimizations Labview makes for parallel tasks.  I never had time to try this, but it might be fun to look into it later.

Many thanks to Bruce for organizing and running this challenge!  I had a great time and learned quite a bit as well.

- Ben.

[Ben]

Congratulations Ben!

I hope my cheering for "Ben" this week-end yields similar results!

Ben

Notes to explain above statement.

This coming Sunday 22 Jan 2006 the Pittsburgh Steelers (Go Steelers!) will play the Denver Boncos in an American style football game. The winner of which will go to the Super Bowl. The quarter back for the Steelers name is Ben Roethlisberger.

Message Edited by Ben on 01-18-2006 09:53 AM

[altenbach]

Congratulations Ben! Very impressive. 🙂 I'd love to see some of the code of the top entries.

Bruce, are you going to write up a summary on the LabVIEW Zone page? This was one of the really great challenges!

---

@shoneill wrote:
That's unexpected.  I was expecting Altenbach to beat me. 

---

Well, I only competed in the early phases with a quick&dirty, back of the envelope, "sieve+trial division".and simply did not have time to work on this further. (I was actually traveling in Japan during the deadline:)). However, I did read up on fast factorizing algorithms and followed this discussion with great interest. Great job, guys!

[daijoubu]

Congratulations Ben!  I hope all the entries will be posted.  I'm looking forward to the next coding challenge.

[alkazaa]

Congratulations Ben!

You beat me with my own (sorry: with Dan Shanks') algorithm. Did you discover it independently?

Anyway, I fully agree with your statement:

---

.....I must stress that the 115x improvement is all due to the algorithm employed, not an overwhelming improvement in coding efficiency.---

---

The final difference in my approach was that I had no 'backup' algorithm (Brent's Rho in your case), so my solution failed for the (few) pathological numbers. I also did not have the time to finish the SQUFOF version with multipliers. Otherwise we seem to have worked along similar lines (Eratosthenes, trial division, Rabin-Miller).
I wanted to upload my solution here, but found quite some chaos on my hard disk (having touched some of my VIs with LV8 in the meantime, no backup existing). Maybe Bruce can post my entry? Though it's only second place.


Thanks again to Bruce for organizing this nice challenge, I learned a lot and had a lot of fun!


-Franz