From: Stuart Palin <stuart.palin@0.0>
Subject: Re: [OT] Hints for an algorithm - avoiding O(n^2)
Date: Fri, 12 Mar 2004 12:55:19 +0000
Date: 2004-03-12T12:55:19+00:00 [thread overview]
Message-ID: <4051B337.B0374E2A@0.0> (raw)
In-Reply-To: 7j5s2c.32r.ln@skymaster
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 uniformly 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
next prev parent reply other threads:[~2004-03-12 12:55 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-03-12 9:15 [OT] Hints for an algorithm - avoiding O(n^2) Jano
2004-03-12 11:06 ` Jean-Pierre Rosen
2004-03-12 12:53 ` Stuart Palin
2004-03-12 12:55 ` Stuart Palin [this message]
2004-03-12 13:48 ` Dmitry A. Kazakov
2004-03-17 1:16 ` jtg
2004-03-12 13:30 ` Björn Persson
2004-03-12 13:42 ` James Rogers
2004-03-12 14:29 ` Robert I. Eachus
2004-03-12 23:44 ` Björn Persson
2004-03-13 15:21 ` Robert I. Eachus
2004-03-14 17:27 ` Jano
2004-03-15 5:34 ` Robert I. Eachus
2004-03-14 17:27 ` Jano
2004-03-13 0:12 ` Wes Groleau
2004-03-17 2:24 ` jtg
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox