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,start
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2004-03-12 01:15:37 PST
Path: archiver1.google.com!postnews1.google.com!not-for-mail
From: 402450@cepsz.unizar.es (Jano)
Newsgroups: comp.lang.ada
Subject: [OT] Hints for an algorithm - avoiding O(n^2)
Date: 12 Mar 2004 01:15:37 -0800
Organization: http://groups.google.com
Message-ID: <5d6fdb61.0403120115.7c102e3c@posting.google.com>
NNTP-Posting-Host: 80.81.106.18
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1079082937 16377 127.0.0.1 (12 Mar 2004 09:15:37
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Fri, 12 Mar 2004 09:15:37 +0000 (UTC)
Xref: archiver1.google.com comp.lang.ada:6259
Date: 2004-03-12T01:15:37-08:00
List-Id: <comp.lang.ada>

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).

Thanks!

P.s: It will be programmed in Ada... just to ease the OT a bit :)