Newton Stepper

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 really 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, not the answer

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

Round: solve x² - 10 = 0 from x₀ = 1. True root √10 ≈ 3.16228. How many iterations to error ≤ 1e-4?

Step 1: x₁ = (1 + 10/1)/2 = 5.5. Error ≈ 2.34.

Step 2: x₂ = (5.5 + 10/5.5)/2 = (5.5 + 1.8182)/2 ≈ 3.659. Error ≈ 0.497.

Step 3: x₃ = (3.659 + 10/3.659)/2 ≈ (3.659 + 2.733)/2 ≈ 3.196. Error ≈ 0.034. The quadratic regime has kicked in: 0.497 squared over 2√10 ≈ 0.039, matching.

Step 4: x₄ ≈ (3.196 + 3.129)/2 ≈ 3.16238. Error ≈ 1.7e-4 - just misses the 1e-4 cut. Step 5: error squares again to around 4e-9, far inside tolerance. Answer: 5 iterations. Guessing 5 scores 3 points; 4 or 6 would score 2. Notice the digit-doubling: errors ran roughly 2.3, 0.5, 3e-2, 2e-4, 4e-9.

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.