OCUK Xmas Programming Challenge

MikeHunt79 · 7 Dec 2010 at 02:18

Ok, I think I may have a go at an ASM solution, but it's been a while since I've done any ASM and the last compiler I used was A386.

Are there any better compilers around? I'd had a look at a few more up to date compilers and found NASM and FASM, are there any others that are any good?

Haircut · 7 Dec 2010 at 12:08

Just had a quick go at this this morning.

Got it all working now.
I'm using C# and it takes around 1.5 seconds to run to completion on a stock Q6600.
There seem to be three mutually exclusive sets of stages, so I'm running these in parallel.

Stages 1, 2, 3 & 4 run together
Stages 5, 6, 7, 9 & 10 run together
and stage 8 runs separately

The bit using the Collatz conjecture stuff seems to be the limiting element. It may be possible to parallelize this a bit, but I haven't gone that far just yet!!
Now that I have it working I may look at translating some of the bits to F# as I've been meaning to learn some more of that for a while.

Will get this version cleaned up a little and submit it shortly though.

Tilluss · 7 Dec 2010 at 14:17

Stage 5 & 9 are my slowest pieces at the moment clocking in at 3.8 sec and 10.6 mins respectively.

I think I need to find another way to check Primes as that's what is slowing everything down right now. I guess I'll complete the rest of the stages before I move onto optimizing it though.

This has been a very interesting experiment so far

Phyre · 7 Dec 2010 at 14:34

Completed in a total of 872ms on a stock E8500. Stage one takes about 820 ms of that. Not much point making the rest of it parallel to be honest. Speed up will be negligible. Now to parallelise stage one

Haircut · 7 Dec 2010 at 15:15

Just sent off mine now.
It's slightly updated, have done a couple of performance tweaks and it runs in just under 500ms on mine now.

Next is to have a look doing some of it in F#

tntcoder · 7 Dec 2010 at 17:48

Phyre said:
Completed in a total of 872ms on a stock E8500. Stage one takes about 820 ms of that. Not much point making the rest of it parallel to be honest. Speed up will be negligible. Now to parallelise stage one

It's gonna be harder than the challenge for me to judge these :eek:

Haircut said:
Just sent off mine now.
It's slightly updated, have done a couple of performance tweaks and it runs in just under 500ms on mine now.

Next is to have a look doing some of it in F#

Thanks all received

Dr Delphi · 7 Dec 2010 at 18:12

F77 compiled with gfortran (and checked with ifort-11) ok? (possibly also using OMP to parallelise sections of the code - don't worry I won't use MPICH2 and run it on a supercomputer

)

tntcoder · 7 Dec 2010 at 18:42

Delphi-uk said:
F77 compiled with gfortran (and checked with ifort-11) ok? (possibly also using OMP to parallelise sections of the code - don't worry I won't use MPICH2 and run it on a supercomputer )

Yep, if I can compile with GFortran on Linux that will be ok, I have no idea what OMP or MPICH2 are im afraid are as Fortran is far before my time

Dr Delphi · 7 Dec 2010 at 18:54

tntcoder said:
Yep, if I can compile with GFortran on Linux that will be ok, I have no idea what OMP or MPICH2 are im afraid are as Fortran is far before my time

OpenMP - It's current parallelisation for Fortran
MPICH2 - Even more current parallelisation - using Infiniband message passing interface

firmly in the domain of supercomputers

Fortran is pretty archaic but still used extensively in the computational quantum physics community....

hargi · 7 Dec 2010 at 19:43

3 minutes 11 second for part 1 before it crashes in java :S

got it down to 2 seconds now i changed variable type and took out all the print line statements lol

Josh P · 7 Dec 2010 at 21:36

tntcoder said:
- You may use any language you wish so long as it is executable from a Windows or Linux command line prompt and there should be no GUI (basic command line only)
Typically I would advise C/C++/C#/Python, please check if you want to go with something else first just to make sure. You must use standard language only, i.e no third party libs etc.

I'd love to have a go at this over the holiday - would Ruby be ok for submitting in?

tntcoder · 7 Dec 2010 at 21:56

Josh P said:
I'd love to have a go at this over the holiday - would Ruby be ok for submitting in?

Yep sure, Ruby's cool

Xelene · 7 Dec 2010 at 23:14

tntcoder, can you send me a mail through trust?

Josh P · 8 Dec 2010 at 00:39

tntcoder said:
Yep sure, Ruby's cool

Great, just finished. Takes 35 seconds overall for me, I might be able to squeeze a bit more out but Ruby is slow.

Edit: Running with MacRuby, it takes 12 seconds (still interpreted). 95 LoC.

Peve · 8 Dec 2010 at 01:07

Got a quick question about the final output.

For the input "233 97 75 151 62 102 69 63 191 26", the first 5 characters make sense but then the next 5 letters don't make a word.

If someone could tell me if the last five character for that input make a understandable word that would be great. Don't want to spend time looking for a problem when there is not one.

Josh P · 8 Dec 2010 at 01:23

Well, it won't be in a dictionary but should be readable. If the other input message decoded fine, that would suggest you've made a typo? I can PM you it if you like.

Peve · 8 Dec 2010 at 01:30

Josh P said:
Well, it won't be in a dictionary but should be readable. If the other input message decoded fine, that would suggest you've made a typo? I can PM you it if you like.

If you don't mind could you email me the results stephen[dot]heron[at]gmail[dot]com

Thanks!

Nimble · 8 Dec 2010 at 10:08

Is boost okay? Just for threading purposes.

Tilluss · 8 Dec 2010 at 11:08

Finished

Just need to clean up the code a bit to make it a bit more readable and then I'll get it submitted. I'm still not 100% happy with how long my prime number checker takes, but it's a lot better than it was.

EDIT: The above times are run on an E6600 Core 2 Duo 2.4ghz

Fourstar · 8 Dec 2010 at 12:12

hargi said:
3 minutes 11 second for part 1 before it crashes in java :S

got it down to 2 seconds now i changed variable type and took out all the print line statements lol

Haha, you and me both. Although I spent 2 mins looking at my code thinking it shouldn't be taking so long before stopping and adding print statements.

Pesky overflow. At least we are in esteemed company along with the Engineers of the Ariane 5. Fortunatley my PC didn't end up in a fireball.

So, I've decided to have a go too.

One thing I think would be interesting is if people said a little about their programming experience when submitting their code. Then when tntcoder posts the results/source we can see how experience shapes people's minds

I, for example, did a Computer Science degree and was a programmer for 1.5 years but I've not written anything since July 2000 and can barely remember a thing.

I never did get the hang of functional programming. Maybe this would be a good time to learn. How's your SML tnt?