Page 1 of 2

Computational Problems?

Posted: Mon May 29, 2006 2:47 pm
by AngusL
Can anyone think of some problems (preferably something that's been solved, I'd like to be able to compare notes) that might be interesting to try writing programs for? I'm looking for fairly complex problems - I intend for this program to be running in a distributed environment.

I've not really had much of a look at highly optimizing things yet, but I can't really start doing things unless I know what my goal is. :P (Yes, I could write a library for the distributed system, but I've got fragments of that done already).

Posted: Mon May 29, 2006 3:03 pm
by feyd
I don't understand what you're asking for.

Posted: Mon May 29, 2006 3:04 pm
by onion2k
P=NP

Posted: Mon May 29, 2006 3:29 pm
by AngusL
feyd wrote:I don't understand what you're asking for.
Sorry :oops:

Erm, I suppose in a way I'm looking for ideas for a computing project - but one that is more... mathematical I guess, rather than something applied (i.e. a very clichéd example being generating primes rather than writing, say, a bulletin board).

Posted: Mon May 29, 2006 3:36 pm
by Chris Corbyn
Something I had to tackle a year or so ago: Calculate the position of the sun in the sky (altitude/azimuth) given a longitude, latitude and a time of day and time of year. It's MASSIVELY complex belive me - but maybe that's swung the other way for you? Not sure how complex you want.

Posted: Mon May 29, 2006 3:39 pm
by Roja
The problem is that distributed problems require maximum performance. Being a higher-level language, php is ill-suited to both the performance levels needed, and the distributed nature of those problems.

Take weather modelling for example. It requires enourmous amounts of memory (php can't generally do so), it requires the utmost in performance, and it has to be distributed across a huge number of machines.

You are asking for a problem that is by definition extremely difficult for php to do, but that php could do.

Thats a tough question.

Does it need to be concrete, or abstract? For example, pathfinding is an extremely difficult problem, but without concrete paradigms (a grid, properties for each grid unit, a source and a destination), its fairly meaningless. Worse, the ones that would be useful to solve (a concrete problem) are also ones that don't need to be distributed, and so on.

Posted: Mon May 29, 2006 3:40 pm
by Roja
d11wtq wrote:Something I had to tackle a year or so ago: Calculate the position of the sun in the sky (altitude/azimuth) given a longitude, latitude and a time of day and time of year. It's MASSIVELY complex belive me - but maybe that's swung the other way for you? Not sure how complex you want.
Really? That seems relatively straightforward.

Learning something new everyday!

[[UPDATE]]
Yeah, didn't think it was all that hard: http://aa.usno.navy.mil/data/docs/AltAz.html

It certainly isn't at the level of needing distributed systems.

Posted: Mon May 29, 2006 3:46 pm
by Chris Corbyn
Roja wrote:
d11wtq wrote:Something I had to tackle a year or so ago: Calculate the position of the sun in the sky (altitude/azimuth) given a longitude, latitude and a time of day and time of year. It's MASSIVELY complex belive me - but maybe that's swung the other way for you? Not sure how complex you want.
Really? That seems relatively straightforward.

Learning something new everyday!
I imagined it would be simple before I took on the project but this had to be bang-on accurate. The amount of code written was ridiculous and the mathematics was... well... painful. Things like magentic declination needed to be accounted for, the earth is not a sphere and the sun doesn't travel in a straight line, or a parabola for that matter which also complicates things. I got it working in PHP though, with graphs and everything but it makes me wanna cry just thinking about it :P

I'll have to dig up this old code (all procedural) and see if I can OOP-ize it for fun actually :)

Posted: Mon May 29, 2006 3:48 pm
by AngusL
In terms of complexity, I'm not too bothered if its complex - however something which isn't currently a pure research application (such as the example of N=NP) in terms of solution. The sun problem sounds interesting, actually, and could conceivably have application.

Incidentally, this isn't to be written in PHP. :P I can write PHP but I'm no master at it and certainly wouldn't claim to be a PHP programmer - all I really know is the basic syntax and a million and one variations upon the age-old database-driven website. Which is all I need it for. We're probably talking C, and conceivably assembler in parts if I don't like what the compiler's doing because those are the languages in which I am most comfortable.

Posted: Mon May 29, 2006 3:49 pm
by Chris Corbyn
Roja wrote:Yeah, didn't think it was all that hard: http://aa.usno.navy.mil/data/docs/AltAz.html

It certainly isn't at the level of needing distributed systems.
Maybe not, that doesn't seem to account for magnetic declination though :? But it is a military system. The one I did was aimed at photographers.

Posted: Mon May 29, 2006 3:49 pm
by Roja
AngusL wrote:Incidentally, this isn't to be written in PHP. :P I can write PHP but I'm no master at it and certainly wouldn't claim to be a PHP programmer - all I really know is the basic syntax and a million and one variations upon the age-old database-driven website. Which is all I need it for. We're probably talking C, and conceivably assembler in parts if I don't like what the compiler's doing because those are the languages in which I am most comfortable.
Ah. Then I highly recommend taking a look at the difficult world of pathfinding in games. :)

http://theory.stanford.edu/~amitp/GameProgramming/

Posted: Mon May 29, 2006 3:51 pm
by Roja
d11wtq wrote:Maybe not, that doesn't seem to account for magnetic declination though :? But it is a military system. The one I did was aimed at photographers.
http://stjarnhimlen.se/comp/ppcomp.html#5 seems to cover magnetic declination, and does it in only about 15 equations.

Posted: Mon May 29, 2006 3:59 pm
by Maugrim_The_Reaper
Depends on the level of accuracy required - if you need a quick solution a simplified approach with some assumptions would work. For maximum accuracy the equations are torturous - but are required for certain applications. I doubt NASA would be taking the simplification route.... Same goes for all the planetary bodies... Even then there's bound to be variance - I wonder if PHP can cover General Relativity...:)

Posted: Mon May 29, 2006 4:22 pm
by pickle
Crack DES/Triple DES/AES :twisted:

Posted: Mon May 29, 2006 4:27 pm
by Chris Corbyn
Calculate the answer to Life, The Universe and Everything.