# Look Before You Leap

*Task 3 of 6 · [ODE Integrators](https://gpu.rocks/learn/ode-integrators-62f4a3ff.md) · GPU.js Learn*

Euler's mistake is committing. It reads the slope at the start of the step and
then pretends that slope holds all the way across. The **midpoint method**
(RK2) makes the obvious repair: take a trial *half*-step, read the slope
*there*, throw the trial away, and take the real full step using that better
slope.

Two force evaluations per step instead of one, and the error goes from first order to
**second**: halve `dt` and the error drops by *four*.
Same instrument as the last task; only the number at the bottom changes.

The step sizes are coarser here — 25 to 200 steps, not 50 to 400 — and that is worth
knowing rather than glossing. A convergence study only reads true inside a window. Too
coarse and the leading error term is not yet dominant; too fine and the error sinks into
the rounding noise of the float32 the WebGL backend computes in, and the ratio starts
reporting arithmetic instead of mathematics.

## Figures

- **the trial half-step is thrown away; only the slope it found is kept**

## Goal

**Goal:** replace the Euler step with a midpoint step, and watch the
ratio go from 2 to 4.

## Requirements

- Trial half-step from the start: `midX = x + v·(dt/2)` and `midV = v + a·(dt/2)`, with `a = −x`
- Take the real step with the *midpoint* slopes: `x += midV·dt` and `v += (−midX)·dt`
- Both updates use midpoint values — leaving either one on the start-of-step slope drops you back to first order

## Hint 1 — what the trial step is for

Nothing about `midX` and `midV` survives the step. They
exist only to answer one question — *what is the slope halfway across?* — and
the answer is `midV` for the position and `−midX` for the
velocity.

## Hint 2 — which slope goes where

The state is `(x, v)` and its derivative is
`(v, −x)`. So the midpoint *velocity* drives the position, and the
midpoint *position* drives the velocity. Crossing those over is the single
easiest way to get this wrong.

## Hint 3 — the whole step

```js
const half = dt / 2;
const a = -x;
const midX = x + v * half;
const midV = v + a * half;
x = x + midV * dt;
v = v + -midX * dt;
```

## Same idea elsewhere

A multi-stage integrator has to hold several copies of the state at once, and on a
GPU that is register pressure — the resource that decides how many threads a streaming
multiprocessor can keep in flight. CUDA calls it occupancy, WebGPU and Metal have the same
constraint under different names. It is a real reason production codes sometimes prefer a
cheap scheme with a smaller step to an elegant one with a bigger footprint.

## Starter code

```js
// The same instrument, a better step. 256 oscillators × 4 step sizes.
const gpu = new GPU({ mode });

const errorOf = gpu.createKernel(function (startX, startV, levelSteps) {
  const n = levelSteps[this.thread.y];
  const dt = this.constants.tEnd / n;

  let x = startX[this.thread.x];
  let v = startV[this.thread.x];
  for (let s = 0; s < n; s++) {
    // TODO: one MIDPOINT step.
    //   half-step to (midX, midV), read the slope there,
    //   then take the full step with THAT slope.
    const a = -x;
    x = x + v * dt;
    v = v + a * dt;
  }

  const exact = startX[this.thread.x] * Math.cos(this.constants.tEnd)
              + startV[this.thread.x] * Math.sin(this.constants.tEnd);
  return Math.abs(x - exact);
}, {
  output: [256, 4],
  constants: { tEnd: 5 },
  loopMaxIterations: 200,
});

const errors = await errorOf(startX, startV, levelSteps);

// average the trajectories at each step size, then see what each halving bought
const means = [];
for (let level = 0; level < errors.length; level++) {
  let total = 0;
  for (let i = 0; i < errors[level].length; i++) total += errors[level][i];
  means.push(total / errors[level].length);
  console.log(levelSteps[level] + ' steps: mean error ' + means[level].toFixed(6));
}
for (let level = 1; level < means.length; level++) {
  console.log('halving dt divided the error by ' + (means[level - 1] / means[level]).toFixed(3));
}
```

---

Interactive version: https://gpu.rocks/learn/ode-integrators-62f4a3ff/3

[Previous task](https://gpu.rocks/learn/ode-integrators-62f4a3ff/2.md) · [Next task](https://gpu.rocks/learn/ode-integrators-62f4a3ff/4.md)