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

["Robert I. Eachus" <rieachus@comcast.net>]

Bj�rn Persson wrote:

> If that were true, the moon would orbit the sun and not the Earth (if we 
> ignore the rest of the universe).

Actually it does.  If you compute the gravitational force of the Earth 
on the Moon, and compare it to the gravitational force of the Sun, the 
Sun has a much greater effect.  In fact, the orbit of the Moon around 
the Sun is everywhere convex.

However, back to the OP's question.  The first thing you want to do is 
not use brute force, but use Runga-Kutta for each pair of objects.  This 
makes the calculation about ten times as complex, but gives a much 
better fit.  Second when two objects are "close" you should do the 
Runga-Kutta interpolation much more often.  This usually means 
calculating the effects of all gravitational attractions on the objects 
that are in close proximity more often as well.  (You don't have to do 
the reverse, because the effect of the two nearby objects on remote 
objects will be that of their center of mass.)  Of course you also have 
to allow for the possibility that there are several objects that are 
gravitationally close.  The normal way to do this is to, at the end of 
every major cycle look at the positions of all the objects, and decide 
which ones get the intermediate steps.  It is not worth the effort to 
work with two pairs instead of four 'close' objects.


-- 
                                           Robert I. Eachus

"The only thing necessary for the triumph of evil is for good men to do 
nothing." --Edmund Burke