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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham 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-16 17:14:38 PST Path: archiver1.google.com!news2.google.com!newsfeed2.dallas1.level3.net!news.level3.com!zeus.visi.com!news-out.visi.com!petbe.visi.com!news.octanews.net!proxad.net!newsfeed.tpinternet.pl!news.task.gda.pl!not-for-mail From: jtg Newsgroups: comp.lang.ada Subject: Re: [OT] Hints for an algorithm - avoiding O(n^2) Date: Wed, 17 Mar 2004 02:16:14 +0100 Organization: CI TASK http://www.task.gda.pl Message-ID: References: <5d6fdb61.0403120115.7c102e3c@posting.google.com> <7j5s2c.32r.ln@skymaster> <4051B337.B0374E2A@0.0> NNTP-Posting-Host: pwr74.pwradio.pl Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-2; format=flowed Content-Transfer-Encoding: 8bit X-Trace: korweta.task.gda.pl 1079486077 7246 153.19.176.74 (17 Mar 2004 01:14:37 GMT) X-Complaints-To: abuse@news.task.gda.pl NNTP-Posting-Date: Wed, 17 Mar 2004 01:14:37 +0000 (UTC) User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.6) Gecko/20040113 X-Accept-Language: pl, en-us, en In-Reply-To: Xref: archiver1.google.com comp.lang.ada:6360 Date: 2004-03-17T02:16:14+01:00 List-Id: Dmitry A. Kazakov wrote: > On Fri, 12 Mar 2004 12:55:19 +0000, Stuart Palin > wrote: > > >>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! > > > This is because the third object is within the sphere containing the > first two. If I correctly remember, that is a consequence of the Gauss > theorem. But if you arrange your objects in spheric clusters centered > in their mass centers, so that the interesting object will be outside > of any of them, then the result will hold. Whether that will be better > than O(n**2) is another question. No! According to Newton laws the object can for instance orbit one of the masses, but if you assume you can model the masses with one mass between them, the object could instead only orbit the center (which is actually empty) and could not orbit any of the masses!