[OT] Hints for an algorithm - avoiding O(n^2)

From: Jano (402450_at_cepsz.unizar.es)
Date: 03/12/04 

Date: 12 Mar 2004 01:15:37 -0800

Sorry for the off-topic, but this is the only group I read frequently
that I'm sure is packed with knowledgeable people.

The problem is a simple one: I'm planning to write a simulator of
sideral-like objects using the Newton laws (precision is not a top
priority). The obvious way is to compute the force interactions
between each pair of objects, sum them all, and iterate over... but
this is O(n^2). To be precise, there are n(n-1)/2 forces to be
computed if I'm right (n the number of objects).

I was wondering if you know of another approach more efficient. A
simple hint is enough, I'll look further as necessary once in the
right path.

I'm having some thoughts about making a discrete division of the space
and compute the potential field, but the idea is not mature enough...
I'm not sure if the loss of precision will be too big, or if the
results will not be similar in time (I'm planning to manage about
1000-2000 objects simultaneously).

Thanks!

P.s: It will be programmed in Ada... just to ease the OT a bit :)