2. Simulating Gravity

Now that we know how to simulate a body’s motion in space, let’s consider a group of bodies together, or rather, a system of bodies. Every body in the system exerts a gravitational force on every other body. This means for each body, we must calculate the force it exerts on every other body. Then we accelerate each body and update their positions.

With our two bodies, we have two calculations.

Now if we introduce a third body, we have six calculations.

What about n bodies? We need (n)(n - 1) = n^2 - n calculations. This approach is the brute force approach, because we are calculating every possible force vector in the system.

The brute force approach has a quadratic time complexity. If we say. That it takes 1μs to make a single force calculation, then a system of 1,000 bodies will require 1,000,000μs = 1s. Not bad. But the Milky Way galaxy has approximately 250 billion stars. This would require 6.25 x 10^22 μs which is approximately 1,981,861,999 years (almost 2 billion!). And this is just for a single step in the simulation.

Obviously, we would like to be able to simulate the motion of our galaxy (who wouldn’t?). The question is, how can we reduce the calculation time down to something reasonable? This is what the N Body Problem is all about.