python-nbody-barnes-hut-gravity-octree
The solution is complete and verified.
Deliverables (in ~):
- SOLUTION.md — the full diagnostic document: title, root-cause analysis, complete runnable code, and a verification section.
- barnes_hut.py — the working simulator.
Root-cause fixes identified:
1. Opening criterion: used max(sx,sy,sz) (half-extent) → 4.4% RMS error; fixed to full side length s² < theta²·d², bringing theta=0.5 to 0.55% (< 1%).
2. Self-force bug: cells containing the target were collapsed including the target's own mass → now the target's octant is always descended to a leaf.
3. Infinite subdivision for coincident particles → exact coordinates merged (physically lossless since mutual force is zero) + depth-capped overflow bucket.
4. Zero-softening/zero-distance division → guarded d2 != 0.
5. Single-node / all-coincident trees → explicit all-zero fast path.
6. Performance → precomputed normalized COM & s², squared-form opening test (fewer sqrt), inlined leaf test.
Verified results:
| Requirement | Result |
|---|---|
| Force accuracy @ theta=0.5 | 0.55% RMS (<1%) |
| Coincident / single-node / zero-softening | exact / 0 / finite ✅ |
| Energy conservation (500 steps, virialized Plummer) | 0.046% band |
| 100k-body step | tractable with tree (~50 s/force) vs 5×10⁹ brute-force pairs (infeasible) |
The exact code embedded in SOLUTION.md was extracted and re-run to confirm it reproduces every result (deliberately noted in the doc's verification section).
# Evidence - Problem class: python-nbody-barnes-hut-gravity-octree - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-27T22:27:37.353Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a Barnes-Hut N-body simulator in pure Python (no numpy): build an octree over 3D point masses, compute forces with center-of-mass approximation controlled by opening criterion theta, and integrate with a symplectic velocity-Verlet integrator. Validate force accuracy against direct O(n^2) summation (<1% RMS error at theta=0.5), energy conservation over long runs, and handle degenerate cases (coincident particles, zero softening, single-node trees). Performance target: 100k particles per step with the tree, where brute force is infeasible at that size.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-nbody-barnes-hut-gravity-octree", "provider": "openrouter", "solved_at": "2026-08-27T22:27:37.353Z", "version": "3.11"}The solution is complete and verified.
Deliverables (in ~):
- SOLUTION.md — the full diagnostic document: title, root-cause analysis, complete runnable code, and a verification section.
- barnes_hut.py — the working simulator.
Root-cause fixes identified:
1. Opening criterion: used max(sx,sy,sz) (half-extent) → 4.4% RMS error; fixed to full side length s² < theta²·d², bringing theta=0.5 to 0.55% (< 1%).
2. Self-force bug: cells containing the target were collapsed including the target's own mass → now the target's octant is always descended to a leaf.
3. Infinite subdivision for coincident particles → exact coordinates merged (physically lossless since mutual force is zero) + depth-capped overflow bucket.
4. Zero-softening/zero-distance division → guarded d2 != 0.
5. Single-node / all-coincident trees → explicit all-zero fast path.
6. Performance → precomputed normalized COM & s², squared-form opening test (fewer sqrt), inlined leaf test.
Verified results:
| Requirement | Result |
|---|---|
| Force accuracy @ theta=0.5 | 0.55% RMS (<1%) |
| Coincident / single-node / zero-softening | exact / 0 / finite ✅ |
| Energy conservation (500 steps, virialized Plummer) | 0.046% band |
| 100k-body step | tractable with tree (~50 s/force) vs 5×10⁹ brute-force pairs (infeasible) |
The exact code embedded in SOLUTION.md was extracted and re-run to confirm it reproduces every result (deliberately noted in the doc's verification section).
# Evidence - Problem class: python-nbody-barnes-hut-gravity-octree - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-27T22:27:37.353Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a Barnes-Hut N-body simulator in pure Python (no numpy): build an octree over 3D point masses, compute forces with center-of-mass approximation controlled by opening criterion theta, and integrate with a symplectic velocity-Verlet integrator. Validate force accuracy against direct O(n^2) summation (<1% RMS error at theta=0.5), energy conservation over long runs, and handle degenerate cases (coincident particles, zero softening, single-node trees). Performance target: 100k particles per step with the tree, where brute force is infeasible at that size.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-nbody-barnes-hut-gravity-octree", "provider": "openrouter", "solved_at": "2026-08-27T22:27:37.353Z", "version": "3.11"}