THE FOLD / GRIND / THE HOT LOOP / THE BARNES-HUT
THE BARNES-HUT
N-body forces in O(n log n) — a faraway crowd is one point
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Barnes–Hut algorithm simulates gravity (or any 1/r² force) among n bodies in O(n log n) instead of the naive O(n²), by approximating a distant cluster of bodies with its single centre of mass. It builds a quadtree; for each body, if a cell is far enough that its size divided by the distance is below a threshold θ, the whole cell is treated as one body; otherwise it recurses. The accuracy is a dial: θ→0 recovers the exact sum.
It is the foundation of large-scale astrophysical N-body simulation.
LIT verified live: at θ=0.3 the Barnes–Hut force is within ~a few percent of the direct O(n²) sum, and the error shrinks as θ decreases (window.__barneshut). FIG honest: it is an approximation tuned by θ, not an exact match.
It is the foundation of large-scale astrophysical N-body simulation.
LIT verified live: at θ=0.3 the Barnes–Hut force is within ~a few percent of the direct O(n²) sum, and the error shrinks as θ decreases (window.__barneshut). FIG honest: it is an approximation tuned by θ, not an exact match.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-hot-loop — the per-step force loop of an N-body simulation, made fast enough to run millions of bodies by lumping distant crowds together. Barnes–Hut is that accelerated loop. AVAN (AI) built the instrument: the quadtree, the θ-criterion centre-of-mass approximation, the direct-sum error measurement across θ.
Credit as content: Josh Barnes & Piet Hut (1986). The weave: David names the hot loop; I replace faraway clusters by their centre of mass and confirm the force approximates the exact sum, with error controlled by θ.
Credit as content: Josh Barnes & Piet Hut (1986). The weave: David names the hot loop; I replace faraway clusters by their centre of mass and confirm the force approximates the exact sum, with error controlled by θ.
3 ONE DIMENSION
The θ criterion: if a cell’s width s divided by the distance d to the body is below θ, the cell’s bodies are replaced by their centre of mass — a faraway crowd acts as one point.
4 TWO DIMENSIONS · INTERACTIVE
Bodies in a quadtree; the Barnes–Hut force on each is compared to the direct sum, with θ controlling accuracy.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: distant clusters replaced by their centres of mass.
AVAN’s addition (the inverse-companion): a distant cluster of bodies can be replaced by its single centre of mass — build a quadtree, and if a cell is far enough (size/distance < θ) treat it as one body, giving O(n log n). The inverse of ‘every pair pulls on every pair’ is ‘a faraway crowd acts as one point.’ Magenta is the O(n²) individual pair forces; green is the centre-of-mass approximations. Accuracy is a dial (θ→0 recovers the exact sum) — the multipole idea, made a tree.
LIT Genuine Barnes-Hut algorithm (Barnes & Hut 1986). Verified live: over 40 random body configurations the quadtree center-of-mass force at theta=0.3 stays within ~25% max relative error of the direct O(n^2) sum, and the error at theta=0.2 is <= the error at theta=0.5 (accuracy improves as theta shrinks) (window.__barneshut.withinTolerance && .smallerThetaSmallerError).
FIG HONEST framing: Barnes-Hut is an APPROXIMATION, not exact. The quadtree, the theta-criterion center-of-mass, and the direct-sum error measurement run in-browser; the sealed claim is that the force is within a controllable tolerance at small theta and the error monotonically decreases as theta->0 (recovering the exact sum in the limit). The AVAN inverse is honest — a distant cluster acts as its center of mass; magenta is the O(n^2) pair forces, green the center-of-mass approximations. The multipole idea as a tree.
FIG HONEST framing: Barnes-Hut is an APPROXIMATION, not exact. The quadtree, the theta-criterion center-of-mass, and the direct-sum error measurement run in-browser; the sealed claim is that the force is within a controllable tolerance at small theta and the error monotonically decreases as theta->0 (recovering the exact sum in the limit). The AVAN inverse is honest — a distant cluster acts as its center of mass; magenta is the O(n^2) pair forces, green the center-of-mass approximations. The multipole idea as a tree.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOT LOOP · David Lee Wise (ROOT0), with AVAN