Prime Factor Coding Challenge

[chilly_charly]

I'll try to negociate with Bruce and see if he can accept the time has :
t = t(with errors) x 100 / (100 - error number) 🙂

Christian, what is your last score with the prime generation ? or have you given up ?

[shoneill]

I think Bruce has the list rodered from easy to hard on purpose.

He's leaving plenty of free room for alternative ways of doing things, such as incrementing the prime number list each iteration or something similar.  The challenge explicitly lists a series of 16-digit numbers of increasing difficulty.

I think we can expect something similar to the test VI.

Shane.

[shoneill]

OK, new results for now....

I've optimized my prime pactorization part down to just over 2 seconds.  Prime generation is still killing me though.  Still waiting on the new algorithm.  I really hope the new algorithm is faster then the old one :D.

As usual, P4 2.8GHz, 1Gig RAM.

Shane.

[Ben]

Do I detect the leaders faltering?

Hmmm, I may still have a chance.

Ben

[shoneill]

Just for completeness,

My "Chaos" time on my machine is stuck at 140ms.  Like I said previously, the prime generation is killing me at the moment.

I'm hoping for a major improvement in my next version.  Whenever that might be.

Shane.

[altenbach]

---

@chilly charly wrote:
I'll try to negociate with Bruce and see if he can accept the time has :
t = t(with errors) x 100 / (100 - error number) 🙂

Christian, what is your last score with the prime generation ? or have you given up ?

---

My vote would be that each wrong answer costs a one minute penalty 😮

No, I haven't given up but I don't have much time at the moment. I do have versions that runs at 1.48 and 1.625 alt, respectively, but I don't like them. Of course I also implemented some great ideas that turned out to be sub-alt. 😞

[bsquared]

I have been working on this challenge here and there for a couple days now, but only recently stumbled apon this discussion thread.  My question is this, not intending to start a flame war: why this specific challenge for Labview?  anyone seriously interested in integer factorization would almost immediately turn to C or fortran or even assembler.  I am *not* a labview expert by any means, so this is an honest question.  Is the interpreter or compiler associated with labview such that it can compete with these other languages?  I have some numbers to back this up, because i happen to have written a library in C to do just what this challenge is asking for, and it will complete all 100 factorizations given in the example file in well under a second.  my (admittedly very unoptimized) labview version takes on the order of minutes to do the same thing. 

that said, i will probably (time permitting) continue to try to get better times using labview.

cheers,

- ben.

[alkazaa]

---

@bsquared wrote:

I have been working on this challenge here and there for a couple days now, but only recently stumbled apon this discussion thread.  My question is this, not intending to start a flame war: why this specific challenge for Labview?  anyone seriously interested in integer factorization would almost immediately turn to C or fortran or even assembler.  I am *not* a labview expert by any means, so this is an honest question.  Is the interpreter or compiler associated with labview such that it can compete with these other languages?  I have some numbers to back this up, because i happen to have written a library in C to do just what this challenge is asking for, and it will complete all 100 factorizations given in the example file in well under a second.  my (admittedly very unoptimized) labview version takes on the order of minutes to do the same thing. 

that said, i will probably (time permitting) continue to try to get better times using labview.

cheers,

- ben.

---

That is indeed a good question. I guess people like this sort of  competition just for that reason: because it is a competition.
And of course it is interesting (at least for the Labview aficionados) to see how close LV can approach C or whatever high level language (it certainly will never beat them).

You mention a code written in C that does it under a second and a Labview code taking minutes. Are both using the same algorithm? It seems to me that such a big difference should not occur when the LV program is properly written.


It just now happened that I finished my LV factorizer and it factorizes the 100 numbers in ~ 180 msec (on 2.3 GHz machine). I would be interesting to write the same code in C to get a comparison but unfortunately my C is quite rusty after years of using Labview. I don't even have a C compiler available at the moment.

This is the timing curve I got:

((see attached .png image, I still don't know how to embed it here directly))



This might be the fastest VI published so far, but I guess Bruce (who fortunately is not a competitor) has a VI which is at least 10 times faster.




My apologies to the others i this forum thread for not taking part in the discussions so far, but instead  lurking in the background. Mostly the discussions were on issues not related directly to the challenge,  like e.g. how fast lists of primes can be generated. I guess the fast factorizing algorithms use prime number lists and trial division only for the lowest primes up to, say, 1000 or 10000.  I use in my approach a list of all primes < 10000, but it does not make a difference in timing whether I store that list or generate it during the first run. To generate the list I use a simple 'Sieve of Eratosthenes' implementation which is not nearly as fast as, e.g., altenbach's. The 'real' algorithms (just google around and you'll find them) don't use lists.


-Franz

[shoneill]

" This might be the fastest VI published so far"

Erm, yes that's one way of putting it.

Nice job.

I think we have a new target  people.

Shane.

[chilly_charly]

---

fahlers a écrit:
...It just now happened that I finished my LV factorizer and it factorizes the 100 numbers in ~ 180 msec (on 2.3 GHz machine)...

---

Ouououffff... Congrats !

I'm going to bed. Don't forget to wake me up after december the 2nd...

Message Edité par chilly charly le 10-20-2005 08:42 PM