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-7-bit X-Google-Thread: 103376,c212e60d58417232 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2004-03-16 18:22:50 PST Path: archiver1.google.com!news2.google.com!fu-berlin.de!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 03:24:39 +0100 Organization: CI TASK http://www.task.gda.pl Message-ID: References: <5d6fdb61.0403120115.7c102e3c@posting.google.com> NNTP-Posting-Host: pwr74.pwradio.pl Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Trace: korweta.task.gda.pl 1079490168 28229 153.19.176.74 (17 Mar 2004 02:22:48 GMT) X-Complaints-To: abuse@news.task.gda.pl NNTP-Posting-Date: Wed, 17 Mar 2004 02:22:48 +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: <5d6fdb61.0403120115.7c102e3c@posting.google.com> Xref: archiver1.google.com comp.lang.ada:6362 Date: 2004-03-17T03:24:39+01:00 List-Id: Jano wrote: > Sorry for the off-topic, but this is the only group I read frequently > that I'm sure is packed with knowledgeable people. > > 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). > > I was wondering if you know of another approach more efficient. A > simple hint is enough, I'll look further as necessary once in the > right path. > > I'm having some thoughts about making a discrete division of the space > and compute the potential field, but the idea is not mature enough... > I'm not sure if the loss of precision will be too big, or if the > results will not be similar in time (I'm planning to manage about > 1000-2000 objects simultaneously). > Two ideas 1. You can assign groups of objects. For every group you can calculate its mass and the center of the mass. Then you calculate acceleration between all the objects in the same group, and then acceleration between all the groups. Of course you apply group acceleration to every object in that group. For instance you can assign sqrt(N) groups of sqrt(N) objects, and then you have O(sqrt(N)^2) + sqrt(N)*O(sqrt(N)^2) = O(N*sqrt(N)) But there are still some problems to solve for instance group boundary can divide two masses which are close to each other. You can use for instance more intelligent clustering algs, skip group interaction between adjacent groups (calculating object interactions instead) or even apply more levels of complexity (objects, small groups, bigger groups etc.) 2. You are going to make a simulation, but you think only about static calculation of gravity forces. Wrong! It is possible to do the calculations between objects much less frequently, while mantaining accuracy and fluent object movement, if you use some tricks. For instance you can adaptively change time step, making it small when needed (if two masses come very close, you calculate their paths more precisely). This will protect your simulation when two masses go very close. You can also make some asynchronous calculations (not in time steps), i.e. calculate gravitational pull for every object, in every time step just integrate it, and from time to time update it - more frequently for close objects, less frequently for distant objects. However it is memory intensive. Connecting these two ideas would be VERY effective. Of course you can calculate group interactions less frequently than object-in-group interactions. And since you can treat each group as single object, asynchronous calculations do not demand much memory in this case. If you find these ideas helpful, please e-mail me, I'm curious about the results. :-)