Prime Factor Coding Challenge

[chilly_charly]

I think it would be unfair to hide in the background, sweating to beat Altenbach's score.

I have just commited a small vi that is 20 % faster than the chaostimer.vi.

Takes 90 ms for all primes up to 2.4 M (Athlon 2.6 GHz-512 Mo).

I think I can save another 20 %. May be I'll be able to produce some more code before december...

[altenbach]

Finally we're getting some action here. Thanks CC. 🙂

Of course you assume that I did not improve my algoritm since then... that posted VI was just a "baseline". (Without diagram, your's is 18k, mine only 13k!) ;).

You don't seem to trust passwording the diagram. Why did you have to remove the diagram, now we cannot convert it to other LabVIEW version. 😞

OTOH, your filename is a bit too telling. You are actually using a sieve??? 😮

Message Edited by altenbach on 10-07-2005 02:45 PM

[altenbach]

WAIT!!!!

You're cheating! You only calculate the primes up to 2'000'000, not 2'400'000!

(You should also format the output as I32, not U32 to be compatible with the challenge.)

[chilly_charly]

---

altenbach a écrit:

Finally we're getting some action here. Thanks CC. 🙂

Of course you assume that I did not improve my algoritm since then... that posted VI was just a "baseline". (Without diagram, your's is 18k, mine only 13k!) ;).

You don't seem to trust passwording the diagram. Why did you have to remove the diagram, now we cannot convert it to other LabVIEW version. 😞

OTOH, your filename is a bit too telling. You are actually using a sieve??? 😮

---

No assumption here. Just using your vi as reference. Sure you improved your coding (BTW, doublecheck your coding style... Ben is lurking around...)

I'm using the Erathostene sieve. No need to keep that a secret. Of course there are some faster methods, but, as you said, it's a baseline.

[chilly_charly]

---

altenbach a écrit: You're cheating! You only calculate the primes up to 2'000'000, not 2'400'000!

---

Sorry ! I'm not cheating, the previous version was just a reckless act, actually faster than the announced 20 % !

Here is a true 2.4M version, with passworded diagram and I32 output.

And I don't care about being bigger if I'm smarter 😉

Message Edité par chilly charly le 10-08-2005 01:21 AM

[altenbach]

Ahh, that's better 😄

And ... more surprisingly... the resulting output array is now identical to my version. 🙂 (maybe we're both making the same mistakes...)

[chilly_charly]

---

altenbach a écrit: And ... more surprisingly... the resulting output array is now identical to my version. 🙂 (maybe we're both making the same mistakes...)

---

That's normal : I'm using your array as reference. As long as my results differ from yours, I add wires here and there until things become  identical. 🙂

Hope you don't mind being the reference for timing and results. I propose to use the Altenbach (symbol Alt) as unit.

My vi runs at 0.78 Alt. 😄

Alternatively, you could consider that your vi is running at 1.28 CC :D:D:D

Message Edité par chilly charly le 10-08-2005 09:01 AM

[Dynamik]

Hi folks,

Can't help staying tuned to this thread - have to confess I'm still looking at it.  Also, found a Quadradic-seive for dummys web-page...

Thanks for making it clear where "the bar" is!

Cheers

Message Edited by Dynamik on 10-08-2005 03:12 AM

[chilly_charly]

Down to 0.72 Alt

[altenbach]

---

@chilly charly wrote:
As long as my results differ from yours, I add wires here and there until things become  identical. 🙂

---

Ahh, Darwinian coding! 🙂 I'm trying to stay away from Intelligent Design myself. I just randomly code, and then it's "survival of the fitfastest". 🙂

Now, how do you measure the speed? I have found that if I use "continuous run" with my posted Chaos timer, the time per iteration goes to a stable number that is much lower than when I do a single run (Single run 140ms average, continuous run 65ms average (1.6GHz Pentium M). Somebody better explain to me what's going on here!!!

Let's not forget that the challenge is about finding prime factors of big numbers, not about finding primes 😉 However, I think that I hit the wall in the factor finding algoritm, there is little improvement left, no matter what I do (still have some ideas left, though!). All the big improvements will come from the prime finding algorithms.

CC, I like that alt units, but we should define it as the inverse, so a alt=2 would be two times faster and your 72% runs at 1.39 Alt.

Now we can even define SI units such as the mAlt (also commonly known as a "Ben", history is a bit vague about the origin of this term, though :o)).

OK, time to play! The Chaos subchallenge of finding all primes up to 2.4M seems like a good gauge of the quality of the prime generators. Let's try to make some guesses of the ultimate speed achievable with LabVIEW. Will it be 2 alt? 3? 10?

My guess is that somebody will break at least 2 alt, maybe even 10... we'll see! 🙂