Wednesday, February 14, 2007

It's just maths

For various reasons, I have found myself faced with some rather complex problems of a mathematical nature. Namely, what are all the unique combinations of an array of elements [a,b,c,d] => ab, bc, acd & etc etc. You get the idea.

I can compute the answer, but I am using recursion and it breaks my computer quite fast. 8 elements takes 30 seconds and 9 elements ... well, I gave up waiting after 5 minutes.

Some research for a better algorihtm led me to complexity theory and specifically a set of problems known as NP-complete or Non-deterministic Polynomial time.

From our friends at Wikipedia:
In computational complexity theory, NP ("Non-deterministic Polynomial time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. Equivalently, it is the set of problems whose solutions can be "verified" by a deterministic Turing machine in polynomial time.


My knowledge finds it's limit at Wikipedia ... going through some of the theories to try and find some sort apporimation alogirthm is doing my head in. If any of the mathematically inclined what to take a stab at it I will buy you many beers.

Did you know there is such a thing as recreational mathematics?

Madness.

Update: now I am looking at Diophantine linear equations. Don't ask.

8 comments:

elaine said...

what you want is a book called Numerical Recipes in C. There're also versions in C++ and FORTRAN. Oh and I seem to recall you can download chapters from the internet.

Or I can give you the phone number of an ex-boyfriend. He does this shit (but waaaaaay harder) for fun. His idea of a GOOD weekend is to lie down on the loungeroom floor with A2 paper and slve maths problems. Then code them if need be to get a solution.


Insanity.

But yeah. If you need help with this maths bizzo, you know where to find me.

elaine said...

ps I know you won't be coding in any of these languages but the methods and principles will help you out about where to start.

_nothing_ said...

Elaine, you're a genius. I must admit I was hoping you would have some ideas.

I just need the algorithm - the code practically writes itself.

Look what I found out:
http://www.nr.com/

_nothing_ said...

Elaine, you're a genius. I must admit I was hoping you would have some ideas.

I just need the algorithm - the code practically writes itself.

Look what I found out:
http://www.nr.com/

elaine said...

no problem. If it doesn't have what you need, give me more clues and I'll see what else I can think of.

elaine said...

also. Not genius. Just an ex scientician who was made to write code with no one to tell me how to write code.

elaine: ok. how do I go about doing that?

supervisor: go and write some code

elaine: how do I do that? Um I took computational physics in 3rd year but I don't think that's going to help.

supervisor: read the manual. get a book from the library. go away and teach yourself.

helpful.

_nothing_ said...

That's how I feel about this maths malarky ... programmer who has to do maths by reading the manual.

Today I am learning about Permutations.

elaine said...

but maths is logical. if you follow the rules, which admittedly are sometimes absurdly hard, it works. coding isn't like that. coding is like learning a stupid language like english.

you learn the rules but sometimes, for no particular reason, you just can't use them.

maybe i'm just not good at programming.