Prime Factor Coding Challenge

[Ben]

Shane wrote

"
I guess you knew all that though

In fact, I my "new" algorithm is based on some thing similar.  I just need to get around to actually implementing it.

"

No I did not. I was just curious because I thought I noticed a pattern and patterns catch my eye. I did not think it was due to the fact that I am mapping 4 byte values to 3 byte chunks because the interval between "grains" seemed to drift as if there was more than one component that were interacting. The 4 to 3 mapping could be one of the components and the effect of "squaring" the matrix could be the two interacting components but there seems to be more than that.

I would like to  see yours and some of the other approaches after the competition is done. I am sure I will learn something that will interest me but bore and baffle the rest of the peolpe in my life!

Ben

[shoneill]

Hi Ben,

Specifically, you can look HERE.

Don't worry, my algorithm (it's not mine at all, I found a good reference) baffles me too.  I understand just enough to implement it (I think).

Shane.

[ohw313]

Hi Guys,

Been silently battling away.

Have been rather impressed with the giant steps I have been able to make.

My first attempt time was +-70s. Now, with a bit of experimentation and some wild ideas that payed off I have managed to get it down to:

5,8 SEC (FIRST RUN, i.e with LABVIEW just started up).- {P4-2,8 GHZ 1GIG RAM}

Will continue trying but it is small steps now.

Have not seen complete Vi times lately(only the prime 2,4M battle times). Wonder if I am now anywhere close to the leaders.

Have to clean it up and then will submit to Bruce for a time.

Good Luck All.

Jurgen 3 5 7 11 13 17 19 23 29 31 37 39 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109

[shoneill]

Looks good,

I reckon it's there or thereabouts at the moment.

My last run was around 7.5 seconds on a similar machine, but I've since abandoned that algorithm in favour of another which is taking quite some time to implement.

I haven't looked beyond the prime generation part for quite a while now.

Hope to have my new algorithm up and running before next year...... 😄

Shane.

PS how big is your VI?

PPS Is there any difference in executaion times in different versions of LAbVIEW?

[ohw313]

Shane,

MY VI is currently 171KB.

I am running LV 7.1. Will convert and test on 6.1.

So, your new algorithm will be finished next year.....Hmmm, you are not busy trying to solve the Reimann Hypothesis are you?

Probably a better way to spend your time, as last I heard there was still a $1000000 dollar prize.

Good Luck

Jurgen

[altenbach]

Very nice Jurgen. Finally a completely fresh new profile for the timing curve. 🙂 Looks very elegant and efficient, no weird jumps!

Does it look the same on the second run?

I've been working on a VI that uses no memory (well a few kB when running). Since it does NOT store any primes, it has a disadvantage when running the sample set and takes about 20 seconds for all 100 problems. Still, it solves the last problem in under 2 seconds starting with a completely blank slate. (1.6 GHz Pentium M). The image shows a collection of 8 runs. There is no penalty for "first run".

(Yes, I know it is slow on a modern computer! :(. I still have an old Pentium with only 48MB of RAM. I suspect it will do quite well on that while most other solutions would start swapping like crazy ;))

Turn of all caching of primes and see how fast you are! 🙂

Message Edited by altenbach on 10-14-2005 08:41 AM

[ohw313]

HI Altenbach,

Thanks.

I just tried a little bizarre logic and was very suprised at the result

Yes, you guessed it. My second run looks very much like the first. I purposely did not post a second run(Thought it might give people ideas......:and I wanted to enjoy my moment in the sun.......smileyvery-happy:). I however have no Jitter.....Hmmm, I wonder why....

I continue to improve and have just shaved another second off.

Like your idea of using no(or very little memory) for prime storage. I think this technique, if done properly, would crush the opposition on a older machine.

Good Luck

Jurgen

[altenbach]

Very impressive! How does it look if you reverse the array of the 100 problems? 😉

[chilly_charly]

Down to 1.53 Alt on the Chaos subchallenge. And stuck there with the present algorithm.

I'll see if I can find something better...

Except Christian and myself, as anybody else the courage to post his score ? Or do you just hide in the dark ? I'll see if I can find something better...

And BTW, this is what I get on the main challenge (second run). :), on a 1 MHz 64K AppleII 2.2 GHz 512 Mo Athlon

Unfortunately there are some missed numbers :(.  Here is the limit of the stochastic approah... but may be, with some more efforts ?.. who knows ? :D:D:D

Also, I don't think that reversing the array is a viable approach. And beware of solutions that would rely on a specific ordering of the numbers. If I was Bruce, I would scramble the data to dismiss any order specific solution...

Message Edité par chilly charly le 10-19-2005 08:30 AM

[altenbach]

CC,

This looks great, except for the 5% wrong answers. Let's hope it's just an easily correctable edge effect and not some fundamental flaw in the algoritms due to mathematically forbidden shortcuts. 😞

I could write one that that takes about a microsecond to solve all 100 problems incorrectly. 😉