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:52:42 PST Path: archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!diablo.theplanet.net!demorgan.zen.co.uk!zen.net.uk!dedekind.zen.co.uk!news-peer-lilac.gradwell.net!not-for-mail Message-ID: <4051B2D9.2159CFCE@0.0> Date: Fri, 12 Mar 2004 12:53:45 +0000 From: Stuart Palin X-Mailer: Mozilla 4.5 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: [OT] Hints for an algorithm - avoiding O(n^2) References: <5d6fdb61.0403120115.7c102e3c@posting.google.com> <7j5s2c.32r.ln@skymaster> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Original-NNTP-Posting-Host: rc2966.rochstr.gmav.gecm.com X-Original-Trace: 12 Mar 2004 12:47:58 GMT, rc2966.rochstr.gmav.gecm.com NNTP-Posting-Date: 12 Mar 2004 12:52:41 GMT NNTP-Posting-Host: 20.138.254.2 X-Trace: 1079095961 news.gradwell.net 63627 dnews/20.138.254.2 X-Complaints-To: news-abuse@gradwell.net Xref: archiver1.google.com comp.lang.ada:6264 Date: 2004-03-12T12:52:41+00:00 List-Id: 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