N-Body Simulation

Simulate a system of N bodies interacting under Newtonian gravity in 2D. Each body has a position, velocity, and mass.

Problem Description

Given an initial configuration of N bodies with positions, velocities, and masses, simulate their gravitational interaction over T time steps using a fixed time step dt. You may choose the number of bodies N and number of steps T as long as the simulation completes within the time limit.

The gravitational force on body $i$ from all other bodies is computed as:

$$\mathbf{F}_i = G \sum_{j \neq i} \frac{m_i m_j (\mathbf{r}_j - \mathbf{r}_i)}{|\mathbf{r}_j - \mathbf{r}_i|^3}$$

where:

• $G$ is the gravitational constant (set to 1.0 for simplicity)
• $m_i$ is the mass of body $i$
• $\mathbf{r}_i$ is the position vector of body $i$

The velocity is updated using:

$$\mathbf{v}_i(t+1) = \mathbf{v}_i(t) + \frac{\mathbf{F}_i}{m_i} \cdot \texttt{dt}$$

The position is updated using:

$$\mathbf{r}_i(t+1) = \mathbf{r}_i(t) + \mathbf{v}_i(t+1) \cdot \texttt{dt}$$

Input

• d_positions: Initial positions of size $N \times 2$ (x, y coordinates)
• d_velocities: Initial velocities of size $N \times 2$ (vx, vy components)
• d_mass: Masses of size $N$
• N: Number of bodies
• T: Number of time steps
• dt: Time step size

Output

• d_output: Positions at all time steps of size $T \times N \times 2$
  • For each time step $t$ from 0 to $T-1$, store the positions of all N bodies
  • d_output[t, i, :] contains the (x, y) position of body $i$ at time step $t$

Implementation Notes

• The problem involves $O(N^2)$ force calculations per time step
• Each body interacts with every other body through gravity
• Consider using shared memory or other optimizations to handle large N efficiently
• Softening can be added to avoid singularities when bodies get very close: replace $|\mathbf{r}_j - \mathbf{r}_i|^3$ with $(|\mathbf{r}_j - \mathbf{r}_i|^2 + \epsilon^2)^{3/2}$ where $\epsilon$ is a small softening parameter