Newton Stepper Guide - Quadratic Convergence

How it works

Each round draws a random integer a from 3 to 20 and asks you to solve x² - a = 0 - that is, find √a - by Newton's method starting from the fixed point x₀ = 1. Before seeing any step, you type your estimate of how many iterations it takes for the iterate to land within 1e-4 of the true root.

The update rule is Newton's method on f(x) = x² - a with f'(x) = 2x: xₙ₊₁ = xₙ - (xₙ² - a)/(2xₙ). The engine runs up to 20 steps, stopping at the first step whose absolute error |xₙ - √a| is at or below 1e-4, and counts how many steps that took.

After you lock in a guess, the reveal shows the true root, the actual iteration count, and the full step table - each iterate with its error - so you can watch the error collapse. Then a fresh a arrives.

How scoring works

Points depend on how far your guess is from the actual count: exact earns 3, off by one earns 2, off by two earns 1, further off earns 0. Score accumulates across rounds; the reveal styles your answer as correct at 2 or more points.

The update rule as a tangent line, and as the Babylonian mean

Newton's method linearizes: from xₙ, follow the tangent of f down to zero. For f(x) = x² - a that gives xₙ₊₁ = xₙ - (xₙ² - a)/(2xₙ), which simplifies to the Babylonian form xₙ₊₁ = (xₙ + a/xₙ)/2 - the average of a guess and a divided by the guess. If xₙ overshoots √a then a/xₙ undershoots it, and their mean is much closer.

The Babylonian form also shows the method overshoots to the high side: by AM-GM, (xₙ + a/xₙ)/2 ≥ √a for any positive xₙ, so after one step every iterate sits above the root and decreases monotonically toward it. From x₀ = 1 (below the root for a ≥ 3), x₁ = (1 + a)/2 jumps above the root, and everything after is a controlled descent.

That first step is worth computing in your head: x₁ = (1 + a)/2. For a = 16, x₁ = 8.5 against a root of 4 - the error after one step is about 4.5. Your iteration estimate is a question about how fast that remaining error dies.

Quadratic convergence: error squaring and digit doubling

Near the root, Newton's error obeys eₙ₊₁ ≈ eₙ²/(2√a): each iteration roughly squares the error (scaled by the curvature-to-slope ratio f''/(2f') = 1/(2x)). Squaring a small error doubles the number of correct digits per step - error 1e-1 becomes about 1e-2 to 1e-3 in one step, then 1e-5 the next. This is why Newton counts are always small: once the error is below about 1, two to three more steps finish the job to 1e-4.

The budget therefore splits into two phases: getting near the root from the deliberately awkward x₀ = 1, then the quadratic endgame. The first phase is governed by the Babylonian halving-like descent from x₁ = (1+a)/2; each early step roughly halves the distance while the iterate is still far above the root (for large xₙ, the update is close to xₙ/2 + a/(2xₙ) ≈ xₙ/2). The second phase is two or three steps, almost independent of a.

So a practical estimator: count roughly how many halvings take (1+a)/2 down near √a, then add about 2. For a in this game's 3-to-20 range that lands at 4 to 6 iterations, with larger a needing slightly more because x₁ starts further from the root. Being within one of the truth - which still scores 2 points - is very achievable with this heuristic.

Why interviewers care about the count

Nobody needs Newton to compute √7 - the point is knowing the convergence regime. Newton is quadratic only once you are close and only when f' is well behaved at the root; far away it can crawl, oscillate, or diverge, and at a root where f' = 0 it degrades to linear convergence. The game's fixed x₀ = 1 exists precisely so the pre-asymptotic phase varies meaningfully with a and the count is not constant.

This is the same machinery under real quant tools: implied volatility is backed out of option prices by Newton (vega is the derivative), yield-to-maturity from bond prices likewise, and multidimensional Newton with the Hessian is the core of second-order optimizers. In every case the practical questions are the ones this game drills - how many iterations, from what starting point, to what tolerance.

Note the engine's one guard: if an iterate is exactly 0 the step would divide by zero, so it resets to 0.5. That is a toy version of a real production concern - Newton implementations always need a safeguard for small or vanishing derivatives.

A worked example

1. The round: solve x² - 10 = 0 from x₀ = 1, which is Newton's method applied to f(x) = x² - a with a = 10. The general update, and this round's starting point:

   $$x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right), \qquad a = 10,\ \ x_0 = 1$$

2. True root and target tolerance - how many iterations until the error drops to 1e-4 or below:

   $$\sqrt{10} \approx 3.16228, \qquad |x_n - \sqrt{10}| \le 10^{-4}$$

3. Iteration 1. The fixed start is deliberately far from the root, so this first jump overshoots past it:

   $$x_1 = \tfrac{1}{2}\left(1 + \tfrac{10}{1}\right) = 5.5, \qquad |x_1-\sqrt{10}| \approx 2.34$$

4. Iteration 2. Still in the pre-asymptotic phase - the error roughly halves rather than squares:

   $$x_2 = \tfrac{1}{2}\left(5.5 + \tfrac{10}{5.5}\right) \approx 3.659, \qquad |x_2-\sqrt{10}| \approx 0.497$$

5. Iteration 3. The quadratic regime has now kicked in: the new error is close to the old error squared, scaled by 1/(2√10) ≈ 0.158, since 0.497² × 0.158 ≈ 0.039 - close to what happens:

   $$x_3 = \tfrac{1}{2}\left(3.659 + \tfrac{10}{3.659}\right) \approx 3.196, \qquad |x_3-\sqrt{10}| \approx 0.034$$

6. Iteration 4. Close, but the error sits just above the 1e-4 line - not done yet:

   $$x_4 \approx 3.16238, \qquad |x_4-\sqrt{10}| \approx 1.7\times10^{-4} \ \ (\text{misses } 10^{-4})$$

7. Iteration 5. One more squaring collapses the error far past the tolerance - this is the digit-doubling that makes Newton's method fast once it locks on. The answer is 5 iterations, and the error sequence (2.3, 0.5, 3×10⁻², 2×10⁻⁴, 4×10⁻⁹) is the signature to recognize on sight:

   $$|x_5-\sqrt{10}| \approx 4\times10^{-9} \ \ll\ 10^{-4}$$

Common mistakes

• Guessing large counts like 10-plus. Quadratic convergence doubles correct digits per step; from x₀ = 1 with a between 3 and 20, the answer lives in single digits.

• Ignoring the pre-asymptotic phase and guessing 2 or 3. The fixed start x₀ = 1 is deliberately far from the root, and the first jump to (1+a)/2 overshoots - the early steps only roughly halve the error.

• Forgetting the count depends on a. Larger a puts x₁ = (1+a)/2 further from √a, typically adding an iteration compared with small a.

• Estimating with the error in f (how far x² is from a) instead of the error in x. The stopping rule is |xₙ - √a| ≤ 1e-4; near the root the f-error is about 2√a times the x-error, which can shift the count by a step.

• Treating a near-miss like an error of 1.7e-4 as done. The rule is at-or-below 1e-4, so one more squaring step is required - exactly the kind of off-by-one that costs a point.

Why interviews test this

Newton's method is a standard numerical-methods screen for quant-research and quant-dev roles: derive the update from a Taylor expansion, state the convergence order, and explain when it fails (bad starting points, vanishing derivative, non-smooth f). The digit-doubling intuition - and being able to estimate an iteration count without running anything - is what distinguishes fluency from recitation.

It also anchors applied follow-ups: solving for implied volatility or yield-to-maturity is Newton in one dimension, and Newton with a Hessian is the reference point that gradient descent and quasi-Newton methods (BFGS) are compared against. Expect the compare-and-contrast question: quadratic convergence per step versus the cost of derivatives per step.

Play Newton Stepper on Outcry

Newton Stepper is free to play on Outcry, in the Gradient Lab section, and every run is timed and scored. Read the guide once, then play Newton Stepper and check your score against the strategy above. The guide book has a written guide for every other game, and the practice hub and mock assessments put the same skills under a real screen's clock.