Simulate gravity between many objects in less than O (n ^ 2) time
I am writing a simulation with n
particles that are all "gravitationally" attracted to each other. To calculate the forces on each particle, I iterate over the list of particles. For each particle in the list, I repeat the same list, calculate the acceleration due to gravity due to each of the other particles, and add each acceleration to the net force on that particle.
While this algorithm works and is more or less accurate, it has a runtime of O (n ^ 2). Is there a faster algorithm?
source to share
For a very large number N, it may be faster to approximate the force of the m-body by creating a grid, and then calculating for each point on that grid the average gravity acting by all particles. You could then look at the particle at the next few grid points and approach the total gravitational force from the particle. However, it will only be faster if the common points on the mesh are less than the number of particles.
Some other approaches are Barnes-Hut modeling and the fast multipole method, but these will accumulate errors over time.
However, depending on the length of your simulation, you will still start to create errors since (almost) all non-integers on the computer are approximate.
source to share