From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FROM_NUMERIC_TLD
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII
X-Google-Thread: 103376,c212e60d58417232
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2004-03-12 04:54:22 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.uchicago.edu!news-xfer.newsread.com!nntp.abs.net!ash.uu.net!lore.csc.com!baen1673807.greenlnk.net!baen1673807!not-for-mail
From: Stuart Palin <stuart.palin@0.0>
Newsgroups: comp.lang.ada
Subject: Re: [OT] Hints for an algorithm - avoiding O(n^2)
Date: Fri, 12 Mar 2004 12:55:19 +0000
Organization: Computer Sciences Corporation
Message-ID: <4051B337.B0374E2A@0.0>
References: <5d6fdb61.0403120115.7c102e3c@posting.google.com>
 <7j5s2c.32r.ln@skymaster>
NNTP-Posting-Host: 20.44.240.14
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: lore.csc.com 1079096060 17342 20.44.240.14 (12 Mar 2004 12:54:20 GMT)
X-Complaints-To: abuse@news.csc.com
NNTP-Posting-Date: Fri, 12 Mar 2004 12:54:20 +0000 (UTC)
X-Mailer: Mozilla 4.5 [en] (WinNT; I)
X-Accept-Language: en
X-Original-NNTP-Posting-Host: rc2966.rochstr.gmav.gecm.com
X-Original-Trace: 12 Mar 2004 12:49:36 GMT, rc2966.rochstr.gmav.gecm.com
Xref: archiver1.google.com comp.lang.ada:6265
Date: 2004-03-12T12:55:19+00:00
List-Id: <comp.lang.ada>

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