Computational Problems?

Ye' old general discussion board. Basically, for everything that isn't covered elsewhere. Come here to shoot the breeze, shoot your mouth off, or whatever suits your fancy.
This forum is not for asking programming related questions.

Moderator: General Moderators

AngusL
Forum Contributor
Posts: 155
Joined: Fri Aug 20, 2004 4:28 am
Location: Falkirk, Scotland

Computational Problems?

Post 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).
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

I don't understand what you're asking for.
User avatar
onion2k
Jedi Mod
Posts: 5263
Joined: Tue Dec 21, 2004 5:03 pm
Location: usrlab.com

Post by onion2k »

P=NP
AngusL
Forum Contributor
Posts: 155
Joined: Fri Aug 20, 2004 4:28 am
Location: Falkirk, Scotland

Post 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).
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post 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.
Roja
Tutorials Group
Posts: 2692
Joined: Sun Jan 04, 2004 10:30 pm

Post 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.
Roja
Tutorials Group
Posts: 2692
Joined: Sun Jan 04, 2004 10:30 pm

Post 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.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post 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 :)
AngusL
Forum Contributor
Posts: 155
Joined: Fri Aug 20, 2004 4:28 am
Location: Falkirk, Scotland

Post 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.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post 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.
Roja
Tutorials Group
Posts: 2692
Joined: Sun Jan 04, 2004 10:30 pm

Post 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/
Roja
Tutorials Group
Posts: 2692
Joined: Sun Jan 04, 2004 10:30 pm

Post 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.
User avatar
Maugrim_The_Reaper
DevNet Master
Posts: 2704
Joined: Tue Nov 02, 2004 5:43 am
Location: Ireland

Post 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...:)
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Post by pickle »

Crack DES/Triple DES/AES :twisted:
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

Calculate the answer to Life, The Universe and Everything.
Post Reply