Hi HN, Inspired by a YouTube video that popped up on my feed (The Fastest Gravity Algorithm You've Never Heard Of: Fast Multipole Method by Keyframe Codes) I decided to write a library implemeting a N-body solver with an O(N) time complexity.

Most real-time physics engines rely on the Barnes-Hut algorithm, which gets the time complexity down to O(N log N). The Fast Multipole Method (FMM) achieves true O(N) scaling, and I decided to write it entirely in C99 as an stb-style single-header library.

I ended up with a implementation, that running a 200,000 particles simulation grants a ~150x better performance than a naive O(N^2) approach, scaling linearly.

One of the downsides with the FFM approach is the cost of generating the octree, but i managed to yield better performance (compared to the naive approach) at as low as 1,000 particles.