Prime Factor Coding Challenge

[BruceAmmons]

Ben,

This is in LabVIEW by definition - NI sponsors LabVIEW coding challenges to see how creative and efficient people can be when using LabVIEW to solve fairly simple problems.

I suspect if your C algorithm is coded efficiently in LabVIEW, its speed will be on the same order of magnitude.  The trick is learning to code efficiently!!  I have always been amazed that minor changes, such as reusing arrays, can make a vi so much more efficient.

Franz,

180 msec is quite impressive!!!  I figured there was a faster way to do it than generating a list of prime numbers and using trial division, but that was all that I had seen so far.  Do you want to send me your version for an official time?

I suspect now folks will start looking at alternative methods for factoring to try to catch up with you.

Bruce

[BruceAmmons]

I still want to see some submissions with prime number generators and trial division.  One of my categories will probably be the most efficient prime number generator up to 100000000, even if that is not the winning technique.  Even if you move on to a new technique, send me your best prime number generator.

Thanks,

Bruce

[bsquared]

both versions use a well known probablistic algorithm and the primes < 10000 generated in insignificant time with the SOE: the size of N doesn't seem to warrant anything more fancy than that.  but i'm pretty sure the LV version is not implemented correctly.

As it turns out, my Labview Kung Fu is quite rusty and not my C.  but you are right, the challenge is interesting in that i am quite curious now how close i can get to my C times. 

By the way, for those of you now rushing off to google "probablistic factorization algorithm" and such... take some time to read into the theory a little.  it can be quite fascinating... or maybe it just is to me.

- ben.

[altenbach]

Bsquared,

Don't uderestimate the power of LabVIEW for problems like that, it can  be competitive with C. (also have a look at this article).

(Besides, even if LabVIEW were slower, it's still a very interesting challeng. NASCAR did not make the Tour de France obsolete ;))

I've implemented a fake LabVIEW factorizer subVI that simply calls a publicly available W32 program (presumably written in C), then parses the output back. It is slower than fahlers (Of course there might be some extra calling overhead).

See attached image of 8 runs (Note that the y axis is linear instead of lograrithmic!).

Also don't forget that LabVIEW gets improves over time. All my entries are about 20% faster under LabVIEW 8.0 compared to LabVIEW 7.1. 😄

Message Edited by altenbach on 10-21-2005 10:44 AM

[alkazaa]

---

@Bruce Ammons wrote:
.
.
.

180 msec is quite impressive!!!  I figured there was a faster way to do it than generating a list of prime numbers and using trial division, but that was all that I had seen so far.  Do you want to send me your version for an official time?

I suspect now folks will start looking at alternative methods for factoring to try to catch up with you.

Bruce

---

Bruce,

I submitted my VIs via NI's 'Submit' link. Should I send you an extra copy or can you get it from there?

I'd also like to comment on my VI a bit, and put the timing into perspective:
the final timing will probably be slightly slower, since in the current approach I use the fact that in the data set as provided by you only a product of two big primes is left after trial dividing by the primes < 10000. Therefore the more complex algorithm is called only once for each number, returning a non-trivial prime and the remaining factor (which also is a prime in the given data set). If you put numbers in your test data having more than 3 primes > 10000 my VI would fail. The final version will not assume that there are only two primes left and it will take a bit longer.

Also the algorithm I employed will fail to factorize a number N of the form N=m² + 1. (Maybe you know by now which algorithm I used ).

I was actually surprised myself how fast the algorithm worked after I had finally taken out all debugging aids. Its ~180 msec  is only a bit slower than Mathematica, which uses 140 msec for that dataset (I always use Mathematica as a reliable reference benchmark). I think the speed comes from the fact that ony I32 arithmetic is used, except for some initalizing code where e.g. floor(sqrt(N)) is calculated.


-Franz

[BruceAmmons]

I haven't talked to NI about forwarding the entries to me, so you should send one directly to me at challenge@ammonsengineering.com.

I don't know which algorithm you used, but I am sure everybody else will figure it out from your clues.

You do have a good point that your algorithm would have more difficulty with 3 primes in the 5 to 6 digit range, which are not currently produced by my problem generator.  You should be prepared to deal with any combination, just in case.  I may modify the problem generator to include different combinations of large primes.

Bruce

[bsquared]

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.

[bsquared]

---

fahlers wrote:

Also the algorithm I employed will fail to factorize a number N of the form N=m² + 1. (Maybe you know by now which algorithm I used ).

-Franz

---

ha ha! yes, i think i do.  trying this algorithm for a certain number of cycles, then switching to a probablistic algorithm for another limited set of cycles would be a good compromise between speed and guarenteeing that the program would finish before the next ice age, with N having any combination of large factors.  finding the optimum number of iterations to run each algorithm would be the challenge.

i am still trying to get the purely probablistic algorithm approach faster at this point...

regards,

- ben.

Message Edited by bsquared on 10-21-2005 03:23 PM

[Ben]

I fnally got around to doing a sieve version and now can generate all of my primes fast enough to concider doing the factoring part.

Still alive,

Ben

[BruceAmmons]

Okay, Franz sent me his latest submission.  It came in at a speedy 139 msec, and all the answers are right.  Franz has told me he is working on a more robust version that can handle all the possibilities, which will probably end up a little bit slower.  It did bring up the need for a couple of rule clarifications, though.

Even if you don't use all the prime numbers up to 100000000, you do need to generate the majority of your prime numbers from scratch.  For example, even if you only use the first 1000 prime numbers, you need to generate most of them (900 or so) using some sort of algorithm.  A table of prime numbers is only allowed when it is the starting point for generating a larger list.  If this still isn't clear, please ask questions.  I realize that this is kind of a moot point, since you can probably generate the primes up to 10000 or so in less than 1 msec, but I want everybody to have the same rules.

I will also request that everybody use the "first call?" primitive (found under synchronization) to initialize their vi.  After you press the run button, the first time the vi is called it will return true.  The rest of the time it will return false.  When you press the run button again, it resets to true again.  This will eliminate my need to close your vi and reopen it every time I run it.

I found the only way I could get consistent times was to use the "run continuously" button.  Each time the test vi ran using this method the time was within a couple of msec.  When I run it using the run button, I had times between 139 msec and 300+ msec.

I will probably modify the test vi and take out the indicators for the final test.  If I am looking for millisecond differences, I don't want to waste any time updating displays.

So now the bar has definitely been raised much higher.  How much faster can we go?  hmmm...

Bruce