Re:CoffeePhysics: A JS/CS Physics Engine
by TheBurningOr on Wednesday February 29, 2012 @10:55AM
(#3648258)
The attraction and collision demos are both doing collision detection, which means N! calculations (for each particle check the location of all the other particles that have not been checked relative to this one). Whereas the chain, cloth and I can't recall the name of the third one, are on the order of N calculations (constant interaction with only a fixed number of other particles).
[ Parent
| on HN ]
Re:CoffeePhysics: A JS/CS Physics Engine
by HardyLeung on Wednesday February 29, 2012 @10:59AM
(#3648283)
You mean N^2, not N!
Re:CoffeePhysics: A JS/CS Physics Engine
by nlogn on Wednesday February 29, 2012 @11:16AM
(#3648346)
He's right actually if the code is written sensibly. Well it should really be (N-1)! but close enough. Think about it in terms of 3 balls. I check ball1 against ball2 and ball3 then move to ball2. It gains me nothing to re-check ball2 against ball1 so I just check it against ball3. When I reach ball3, I have already checked everything and I'm done.
The loop should look like this:
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j)
Re:CoffeePhysics: A JS/CS Physics Engine
by dmvaldman on Wednesday February 29, 2012 @11:24AM
(#3648382)
That's N*(N+1)/2 steps, or order N^2. Best to visualize as the number of entries on the upper triangle of an NxN matrix.
Re:CoffeePhysics: A JS/CS Physics Engine
by HardyLeung on Wednesday February 29, 2012 @12:47PM
(#3648807)
I think you need to revisit your understand of complexity. It is O(N^2). If you want the exact count, it is N(N-1)/2. N! is an exceedingly large number even for very small N.
Re:CoffeePhysics: A JS/CS Physics Engine
by nlogn on Wednesday February 29, 2012 @09:58PM
(#3650736)
Yep I'm wrong. Mixed up factorial just like mistercow said. Thanks for the corrections. And here I was worrying that someone would complain that my loop wouldn't address the issues of collision response necessitating more checks, thus making a recursive solution necessary.