Trading Accuracy for Time

N-body Problem

Computing the pairwise gravitational (or electrostatic) force on each of $N$ particles, given $F=G{m}_1{m}_2/r^2$. Naive implementation is $O(N^2)$ per timestep: every particle sees every other particle. The running example in ECE459 L14 for approximate computing.

Why is the naive version so bad?

Force drops off like $1/r^2$, so faraway bodies contribute almost nothing but still cost the same per-pair arithmetic. Scaling $N$ from 10k to 100k is 100× more work for marginal accuracy gain on the force from faraway clusters.

Binned approximation (center-of-mass)

Exploit the $1/r^2$ falloff: group distant bodies and replace them with a single summary point.

1. Bucket each particle into a cubic bin from its position, bx = floor(x / bin_size). $O(N)$, not a full sort
2. Summarize each bin with total mass + center of mass
3. For each particle $p$ in bin $B$:
   • Near bins ($B$ itself + 26 neighbors in 3D): loop over actual particles, exact force
   • Far bins: one interaction per bin, force from the bin’s center of mass

for each particle p:
    for each neighbor_bin of p.bin:          // exact, ~27 bins
        for each q in neighbor_bin: if q != p: force += exact(p, q)
    for each far_bin:                         // approximate, one call per bin
        force += approx(p, far_bin.cm)

The key efficiency trick: the bin structure tells you where to look, so you never iterate over all far particles individually. Work per particle becomes O(local particles + #bins) instead of O(N).

Why not approximate everywhere?

Center-of-mass averaging breaks down when bodies are close, because $1/r^2$ is very sensitive to the exact $r$ near zero. Replacing a nearby cluster with its center of mass can give wildly wrong forces. Near-field must stay exact.

Measured results (L14)

• 100k points: naive $162$s → binned $147$s single-threaded
• With rayon parallel iterator, both hit $\approx 25$s, parallelism swamps the approximation savings
• Lesson: approximation and parallelism aren’t interchangeable, big problems need both

Would speculation help?

L14 exam question: “could we speculate on whether another point is near or far?”

Not really, because the binned approach is approximation, not speculation:

• Approximation: deterministically choose exact-or-cheap based on computed bin distance
• Speculation: guess far-by-default, use cheap path, recover on misprediction

Speculation is unhelpful here because near/far is $O(1)$ to compute directly from coordinates, so there’s nothing to guess about. Worst case, a “far” mis-speculation gives a large force error (since near-field is where $1/r^2$ is sensitive), and rollback machinery costs more than the check it replaces.

Related classical algorithms

• Barnes-Hut: same idea with an octree instead of uniform bins, $O(N\log N)$
• Fast Multipole Method (FMM): higher-order multipole expansions, $O(N)$
• Both are deterministic approximations, neither speculates

Related

• Trading Accuracy for Time
• Speculative Execution
• Value Speculation
• Loop Perforation