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.1 required=5.0 tests=BAYES_00, PP_MIME_FAKE_ASCII_TEXT 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-14 09:27:25 PST Path: archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newsfeed.vmunix.org!news2.euro.net!news2.euro.net!newshub1.home.nl!home.nl!feeder1.essentkabel.com!news.agarik.com!news.agarik.com!teleglobe.net!teleglobe.net!62.81.31.29.MISMATCH!cyclone.auna.com!twister.auna.com!53ab2750!not-for-mail From: Jano Newsgroups: comp.lang.ada Subject: Re: [OT] Hints for an algorithm - avoiding O(n^2) Message-ID: References: <5d6fdb61.0403120115.7c102e3c@posting.google.com> <7j5s2c.32r.ln@skymaster> X-Newsreader: MicroPlanet Gravity v2.50 Date: Sun, 14 Mar 2004 18:27:20 +0100 NNTP-Posting-Host: 212.97.168.186 X-Trace: twister.auna.com 1079285243 212.97.168.186 (Sun, 14 Mar 2004 18:27:23 MET) NNTP-Posting-Date: Sun, 14 Mar 2004 18:27:23 MET Organization: AUNA TLC Xref: archiver1.google.com comp.lang.ada:6320 Date: 2004-03-14T18:27:20+01:00 List-Id: Jean-Pierre Rosen dice... > > "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. I discussed this too with a colleague, but it's equivalent (apart from the subtleties noted by other posters) in computing time.