Prime Factor Coding Challenge

[shoneill]

Ben,

7.5 seconds for 100M primes on what type of machine?

My sieve takes 3.75 on a P4 2.8GHz.  I reckon there's more headroom left in that too.

My factorization using these primes takes almost exactly 2 seconds (for all 100 numbers).  I've optimized this part, I don't hink I can get much more out of it.

Shane.

[Ben]

Hi Shane,

I think it is a 2.3G laptop.

If you are doing it half the time, that means I am still doing twice as much as I have too!

I guess I could figure out how to do this with concidering even numbers and half split my work but ...

"My brain hurts" (Monty Python?).

Ben

[shoneill]

Ben,

I presume you mean how to do it withOUT considering even numbers.....

It's actually quite easy.  There's a slight overhead in generating the index but it's well worth it.  I don't think I need to tell you any more than that really.....

Another important point is that you should only write values to memory which need to be changed, write operations are generally more expensive than reads.......

Shane.

[BruceAmmons]

Ben Rayner,

I wasn't talking about you, actually.  I was talking about Benjamin Buhrow.  When I posted his time, I didn't realize he was bsquared.  I thought we had a new person joining the fray.

Bruce

[Ben]

This right after I get off of the phone with my customer (another Ben).

At this point I am not sure how many Bens are involved and I am feeling a little light headed

I think I will go study for my CLA, I need the break.

Ben

[chilly_charly]

Thanks to Franz for sharing his findings.

I hadn't find any track leading to the SQUFOF method, but once that door opened, I found a number of missed informations that will be highly valuable ! Unfortunately, I have some difficulties to translate the theory and explanations to a proper LV diagram. I think I'll have to go the hard way : start with C code, try to understand what it does, then figure how to do it properly in LV... 😞

Shonneil, my trial division routine (see answer n° 99 in this thread, and forget about the errors, there was a stupid mistake...) takes 1.66 s for all test numbers on a 2.2 MHz machine (should be 1.3 on yours), so you probably still have some unoptimized parts ;). I also found a claim for an Erathosthène sieve (written in C) running in about 0.2 s for all primes up to 10^8 :o. Mine runs in 4.6 s (should be 3.6 on your machine). That leaves also some room...

The nice thing here is that even with public algorithms and things as simple as the trial division, there are different coding flavors that lead to rather different execution speed !

I like very much this sort of challenge since we are obliged to return to basics and try to understand how things works deep inside. I don't believe that there will be any innovative algorithm created by one of us, and we should concentrate on what is really the heart of this challenge : see how fast we can go with LabVIEW. Discussing the method used is probably the best thing we can do if we want to improve our coding skills. 🙂

[shoneill]

CC,

Sounds like your trial division is going pretty well....  Is that a 2.2 GHz P4 or a Pentium M?  I do know the clock speeds between pentium M and Pentium 4 don't scale linearly.  In fact a 2.2 GHz M is equivalent to a much higher clocked Pentium 4.  I hope you're using a Pentium M 😉

I was pretty much aware that there's plenty of room to improve the sieve part, but I reckon I'll havve to look at my other part too.  Hmm.  I do have code for a very fast sieve, but I haven't gotten around to implementing it fully yet.  Will do.  I'm also working on a probabilistic version which (even if it doesn't beat Fahlers time) looks like it'll comfortably beat my trial division version.

I agree that the "how things works deep inside" is intriguing.  Especially since the G compiler isn't really well documented.  Trial and error (instead of trial division) is required sometimes with surprising results.

Shane.

[chilly_charly]

---

shoneill a écrit:
Sounds like your trial division is going pretty well....  Is that a 2.2 GHz P4 or a Pentium M?  I do know the clock speeds between pentium M and Pentium 4 don't scale linearly.  In fact a 2.2 GHz M is equivalent to a much higher clocked Pentium 4.  I hope you're using a Pentium M ;)

---

It's an Athlon XP2600+... Not sure about the clock rate now... How could I check ? (Don't laugh : remember I'm a Macintosh user...)

[altenbach]

My Athlon XP2500+ runs at 1.83GHz, so yours should be slightly higher. 😉

[Ben]

Does anyone have any ideas what is going on here?

I wrote a VI to time one version of my find primes to another version. As I have been testing I have run across some baffling behaviour. This curiosity is illustrated in the Task Manager >>> Performance diagram below.

It appears the second time I test the two methods, it takes almost twice as long to complete!

System performance and memory usage under varying conditions.

A) At time A I have shutdown all applications and un-plugged my ethernet cable. The application that compares the two mtehods is opened.

B) After letting things settle the test VI is run. The step in memory usage is consistant with first method's memory requirements.

C) A second step in memory usege is consistant with the second method running.

D) The test VI completes and the memory that was allocated durring the tests is released. Total test time run 1 is B to D.

E) THe app and LV are closed. About 100 Meg of memory are released by LV.

F) I noticed that I had started test with setting loop count so I aborted the test run.

G) I open the test VI again and wait for thigs to settle.

H) The test VI is run again and memory is again allocated as was noted at time B.

I) Second bump like C.

J) End of test run #2. Totla run time is H to J.

K) The test VI is run again (Note: Did not unload from memory). Initial bump in memory is again expected.

L) Second bump in memory seems late. the time from K to L is almost double what obesrved at B-C or H-I.

M) End of test VI. Total time K to M is almost double that from test run 1 or 2.

Notes:

Max memory usage was 452Meg and available physical was 458Meg.

The red trace in the Performance plot is the kernal mode time. It appears to be almost double the area in the previous runs.

The Test VI code is here.

And the buffer allocations in both methods of the find prime candidates is here.

So....

Does anyone have an idea why second runs of a VI are so much slower than in itial runs?

Sorry I can not post an example until after the challenge is over

Ben

Message Edited by Ben on 11-05-2005 11:40 AM