News for hackers. Stuff that matters.
Re:JavaScript particle simulator by acadien on Tuesday November 19, 2013 @06:44PM (#6765368)
Galaxies would require coupling of the particles, interactions through gravity... this would kill the efficiency of the solver. N-Particle simulations are always O(N^2) (or more).
Re:JavaScript particle simulator by bochi on Tuesday November 19, 2013 @06:54PM (#6765437)
Re:JavaScript particle simulator by acadien on Tuesday November 19, 2013 @07:05PM (#6765489)
Yes, once you start cutting off long range effects you can improve on the strict O(N^2) limitations.
Re:JavaScript particle simulator by cscheid on Tuesday November 19, 2013 @07:25PM (#6765593)
It's not cutting off. It's replacing many long-range effects with a single one weighted more (and done it carefully so that the floating-point error is literally smaller than you could tell).

There's even better methods that take O(n) time, like the fast multipole expansion ones.

Re:JavaScript particle simulator by darkmighty on Tuesday November 19, 2013 @08:42PM (#6765849)
Btw this goes into numerical analysis, and O(-) is important but so is error convergence. I imagine these big-O figures are for a constant error, but I figure the asymptotic may change behavior as the other parameter changes.
Re:JavaScript particle simulator by ngoldbaum on Tuesday November 19, 2013 @07:30PM (#6765610)
One could also use FFTs and the particle-mesh method or a TreePM method. Basically, the particle masses are deposited on a fine mesh. Poisson's equation gets solved using FFTs and then the particle accelerations are computed by interpolating on the gradient of the potential field.
Re:JavaScript particle simulator by mistercow on Tuesday November 19, 2013 @07:08PM (#6765508)
You could potentially do better than N^2 (ish) by approximating. Quantize the world into a grid, add up mass at each grid point. Then each particle is affected by this weighted grid, which is made up of a relatively small number of pseudo-particles.

Of course, you'd still need to fall back to N^2 for the nearest particles, or the accuracy would be unusably bad. But it's a much smaller N.