OCUK Xmas Programming Challenge

_TubbZ_ · 6 Dec 2010 at 02:04

Oooh I may have a go at this if i get time. With now being in my final year at uni everything has turned to theory and I want to flex my coding brain again! I was thinking about learning SmallTalk for fun (how normal!) over Christmas so I may do it that. If not I think it will have to be plain old ANSI C.

slylittlefox · 6 Dec 2010 at 02:09

Bloomfield said:
2.5Million

And it's less than 3 seconds, it's stage one that takes about 2 of the 3 seconds .

In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast

Bloomfield · 6 Dec 2010 at 02:14

slylittlefox said:
In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast

C++, and yes, computer in sig.

I have no idea what the algorith is tbh, I'd attach the source to prove it, but that'd kinda spoil it for some people

.

You know that it just has to calculate how many numbers are prime between 1 and 2.5 million, and not store/print them yeah?

Edit - I'll try and find out what algorithm it is.

Edit again

- sorry, it adds each prime together, not counts them, that was another stage.

slylittlefox · 6 Dec 2010 at 02:17

Bloomfield said:
You know tha it just has to calculate how many numbers are prime between 1 and 2.5 million, and not store/print them yeah?

That's not how I read it:

Work out the sum of all primes below 2.5 million - this can use your prime testing algorithm from stage 5 expect around 3 minutes computational time (if your algorithms any good!).

e.g Sum of all primes below 10 - Primes are: 2,3,5,7 = 2+3+5+7 = 17

The sum is the answer to this stage.

From that, it's got to keep a running total of the sum of the found prime numbers, not just a simple counter?

slylittlefox · 6 Dec 2010 at 02:18

Just read your second edit

Bloomfield · 6 Dec 2010 at 02:18

slylittlefox said:
Just read your second edit

Yeah, it's late

.

Bloomfield · 6 Dec 2010 at 02:26

I've e-mailed the cpp file to tntcoder, so that he can either confirm what i said is true, or that i've done it all wrong

(this wouldnt surprise me, although it does seem to give the correct answer at the end

).

Nimble · 6 Dec 2010 at 06:52

slylittlefox said:
In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast

Mine takes about a second to do it and that's in Java. As far as I can tell, Lucas-Lehmer is a poor choice for for generating series of primes, as it's designed for testing primality of arbitrary numbers.

tntcoder · 6 Dec 2010 at 07:48

slylittlefox said:
In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast

The reason it's quick here is because we are working with small primes. The largest prime under 2.5 mil is 2499997, that's only a 22-bit number. If I asked you to find the sum of the first 2.5 million >= 1024-bit primes, then that's when things would get harder. So it's not too bad computational complexity wise. You can work out if 2499997 is prime in 1582 loop iterations (less with a better algorithm), so if you work out the algorithm complexity for all numbers 2->2.5mil it isn't as bad as you might imagine.

Bloomfield said:
I've e-mailed the cpp file to tntcoder, so that he can either confirm what i said is true, or that i've done it all wrong (this wouldnt surprise me, although it does seem to give the correct answer at the end ).

(Please just mail to [email protected] as I don't check my hotmail one)

Your code works fine and is correct, nice one

It takes 1.552s on my box, quite impressive! On reflection maybe I should have used larger numbers to make it take longer, will remember that if we ever do this again. I'm going to need a damn accurate timer to do the judging

Your prime testing algorithm is also fine, it's the same one I used. Not sure what it's called either, nice and simple though

Sorry it's a long wait till the 28th, I figured it was best to allow time for people to work on it over xmas holidays

Tilluss · 6 Dec 2010 at 09:01

I was thinking about making something in C++ as a learning project recently, I guess I can have a go at this and see how it goes

Bloomfield · 6 Dec 2010 at 10:17

tntcoder said:
(Please just mail to [email protected] as I don't check my hotmail one)

Your code works fine and is correct, nice one It takes 1.552s on my box, quite impressive! On reflection maybe I should have used larger numbers to make it take longer, will remember that if we ever do this again. I'm going to need a damn accurate timer to do the judging

Your prime testing algorithm is also fine, it's the same one I used. Not sure what it's called either, nice and simple though

Sorry it's a long wait till the 28th, I figured it was best to allow time for people to work on it over xmas holidays

Ah sorry, i just clicked trust, forgot you put the e-mail address in the op

.

NPs about the wait, gives me plenty of time to sort the code out properly

.

s-p · 6 Dec 2010 at 12:21

Spyhop said:
I'm planning to learn a new language in the coming weeks so I might submit a noob-tastic solution in that close to the end.

I hope someone using C# goes LINQ heavy!

I'm just downloading Visual Studio now, so may have a go at the challenge at some point this afternoon. If I do, I'll endeavour to do it in C# with some nice parallel linq for you.

lemonade · 6 Dec 2010 at 13:56

my brain fried at all the numbers and equations

Shadez · 6 Dec 2010 at 14:41

I would love to give this a go, but the last thing im going to want to do over the xmas break is MORE programming.

Got about a million lines of code to write and debug fully, ready for extremely rigourus testing and it all has to be finished before the new year.

Tilluss · 6 Dec 2010 at 15:51

Why did I choose to do this in C++, the things I could normally do easily in C# have been taken away from me!

I've completed 1,2 & 3 so far and it has a run time of about 1040 milliseconds, just starting to look at 4 if I can work out what the bloody hell a factorial is.

EDIT: Scratch that, 4 done now also, was easy as soon as I understood what a Factorial was

Rjindael · 6 Dec 2010 at 19:44

I joined these forums just for this challenge

Should have a solution within the next day or two! gl ^^

tntcoder · 6 Dec 2010 at 19:46

Rjindael said:
I joined these forums just for this challenge Should have a solution within the next day or two! gl ^^

Welcome, thanks for having a go!

Rjindael is a nice cipher

orderoftheflame · 6 Dec 2010 at 21:08

Nice idea, hopefully I can find the time to get an entry in.

Peve · 7 Dec 2010 at 01:09

I have just finished all the steps.

It took my implementation 2.7 seconds to complete the full program with 1.7 seconds of that to find the 2.5 million prime numbers. This is running on a Q6600 @ 3.4GHz.

Quite happy with it but it needs some major tidying up, stage 2 looks terrible

Phyre · 7 Dec 2010 at 01:53

Only done the first stage so far. Takes approx. 700ms currently. Only a first go at it so can probably improve that further.