John VanSickle <evi### [at] hotmailcom> wrote:

> If you have a natural fear of O(N^2) problems, then I have some bad news
> for you.
>
> To accurately calculate the current force on each particle in a system,
> you have to match up every possible pair of particles, all (n^2-n)/2 of
> such pairs, and calculate the force that each of the particles in the
> pair exerts on the other (generally equal and opposite, according to Mr.
> Newton, so there is only one force calculation for each pair).

In all fairness, there are better methods.  Think of dividing all the particles
up into an octree.  A whole group of particles at a distance can be lumped into
one mass.  I guess O(N logN) algorithms like this are as revolutionary as the
FFT.  Of course I'm just regurgitating what's on Wikipedia and haven't actually
done any of this, but it's interesting to think about--and fascinating to watch.
 (See links below)

 - Ricky

http://en.wikipedia.org/wiki/Barnes-Hut_simulation
http://en.wikipedia.org/wiki/Fast_Multipole_Method
http://www.astro.ex.ac.uk/people/mbate/Animations/
http://www.cita.utoronto.ca/~dubinski/nbody/

Post a reply to this message