Sorry, I should have been more clear. My "n" is the number of massive bodies. For my simulations, that means the Sun and between 4 and 8 planets. The reason the problem is O(n^2) is because the gravity of every massive particle affects every other particle. With the Sun and 4 planets you have 5*4 = 20 force calculations. But between 1000 stars (e.g. a star cluster) you have 1000 * 999 = 999,000 force calculations.
There are roughly two common ways to deal with this problem: 1) One way is to make an approximate algorithm that doesn't compute every single force exactly. For example, a tree code is O(n log n) instead of O(n^2). The result is less accurate but it scales better for large "n". This is what you'd use if you wanted to model a galaxy. This may sound strange, but in terms of dynamics, the galaxy is very young. In its entire history, the Milky Way has only gone around about 40 times. 2) The other way is to keep the O(n^2) function but try to call it less often. You do this for problems where a less accurate result is not acceptable. That happens in planetary systems. Because there are many orbits, the errors can really accumulate. If you had an error of 0.00001% per orbit, the result would be completely useless after only a million years. Planet formation takes about 100 million years, and Earth is 4,500 million years old. Cheers, Daniel. On 19 June 2015 at 17:53, Scott Jones <[email protected]> wrote: > Is your 'n' only the planets, large moons, dwarf planets, asteroids, and > the Sun? Or is it the age, that you mentioned was in the billions, for > orbits... (sorry for my dumb questions, but the parallel part of this is > rather interesting to me!) > > On Friday, June 19, 2015 at 10:47:20 AM UTC-4, Daniel Carrera wrote: >> >> >> On 19 June 2015 at 16:20, Scott Jones <[email protected]> wrote: >> >>> Not being an astronomer, I don't know how this is supposed to be, but >>> you have calculations based on the bod array inside the loop, but you are >>> never updating bod... Are you just depending on the compiler to move those >>> out of the loop? >>> >> >> >> Oh, the program is not complete. In a real program the "bod" array would >> be updated elsewhere. Updating the bod requires O(n) additions, >> multiplications and memory look-ups. Computing the forces on each particle >> requires O(n^2) additions, multiplications, divisions and memory look-ups. >> So all attempts at optimization focus on the O(n^2) part, so that's the >> only part that I posted. >> >> Cheers, >> Daniel >> > -- When an engineer says that something can't be done, it's a code phrase that means it's not fun to do.
