◄ WORLD V · SONNY 5DART 559 · a helldive down the well

THE BARNES-HUT a distant crowd is one mass

Simulating a galaxy the brute way is O(n²): every star pulls every other. Barnes-Hut makes it O(n log n) by a lie you can control: build an octree, and if a distant cluster is far enough that its size-over-distance s/d < θ, replace the whole crowd with a single mass at its center of mass. Tune θ and you trade accuracy for speed. It is how galaxies get simulated at all.

THE TECHNIQUE if s/d < θ, treat a cell as its COM

The demo computes a cluster’s center of mass and applies the opening criterion s/d < θ=0.5: live demo







  
HISTORY & CREDIT Barnes & Hut · 1986

  
“Barnes-Hut is exact.” — it is an approximation controlled by θ; θ=0 recovers the exact O(n²) sum. cited

  
the octree · recursively box the space; each cell stores its total mass and COM.
the criterion · far cell (s/d < θ) → one mass; else open it and recurse.
1986 · Josh Barnes & Piet Hut, Nature — O(n log n) N-body.

  
A controlled lie that makes galaxies computable. algorithm






  
RECOMMEND FOR I-13 the opening test, on the compiler

  
On i-13, a 3-body cluster has COM 12.5; with s=4, d=100, s/d=0.4 < 0.5, so treat it as one:

  
$ i13 run gw_barnes-hut.i13
RUN OK · 132 step(s) · call depth 4
center       = 12.5   -- mass-weighted COM
open_ratio   = 0.4    -- s/d
treat_as_one = 1      -- 0.4 < theta 0.5

  
Recommend as a NULL — APPROXIMATION (auto-NULL) + resource (B40). Barnes-Hut computes an approximate force controlled by θ — a different function than the exact sum, so there is no same-function pair; and the COM is a pinned reduction. NULL — a controlled lie.