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

[Stuart Palin <stuart.palin@0.0>]

Jean-Pierre Rosen wrote:
> 
> "Jano" <402450@cepsz.unizar.es> a �crit dans le message de news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
> > 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).
> >
> If I remember my Newton laws correctly, you just need to compute the force
> between an object and the center of mass of all other objects.

No!  It is quite a straight-forward proof to show that for a
point inside a uniformaly dense sphere the mass at a greater
distance from the centre (than the point) has no net
gravitational effect on the point.

Also a counter-example is very easy to construct.  Consider
two large equal masses separated by a large distance.  Their
centre of mass (which will be the sum of their masses) is at
the mid-point of the shortest line joining them.  Another
mass placed a little way from this mid-point will in fact
feel little gravitational effect because the masses are a
long way away.  However, a calculation based on the centre
of mass would suggest there is a very strong force acting!


No help to the OP - they might be better off posting in an
astronomical group as this is more likely to be where people
with knowledge of any special algorithms might hang out.

--
Stuart Palin