Newton vs Bisection

Almost every quantitative question eventually becomes the same one: for what x does f(x) = 0? Where does a rocket's altitude hit the ground, what interest rate makes a loan balance vanish, at what temperature does a reaction flip? These are all root-finding problems, and we rarely have a tidy formula for the answer.

So we hunt for the root by guessing and improving. Two methods from the classical toolbox do this in completely opposite styles. Bisection is the cautious tortoise: it traps the root inside an interval and halves that interval over and over — slow, but it cannot fail. Newton's method is the reckless hare: it follows the curve's tangent straight toward the answer, doubling the number of correct digits each step — blazingly fast, until the day it overshoots and runs off to infinity.

This is the oldest tradeoff in numerical computing: speed versus safety. The happy ending is that, unlike the famous open problems on this site, this one is completely solved — we know exactly when each method works and how fast.

Pick a function, choose where Newton starts, and press Step to advance both methods one iteration at a time — or Run to let them race. The table shows each method's current estimate and how far it still is from the true root.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{label_fn}}
    <select id="fn">
      <option value="cos">{{opt_cos}}</option>
      <option value="cubic">{{opt_cubic}}</option>
      <option value="atan">{{opt_atan}}</option>
    </select>
  </label>
  <label>{{label_x0}}
    <select id="x0">
      <option value="1">{{opt_x0_1}}</option>
      <option value="1.3">{{opt_x0_13}}</option>
      <option value="2">{{opt_x0_2}}</option>
    </select>
  </label>
</div>
<table class="race">
  <thead><tr><th>{{th_step}}</th><th>{{th_bis_x}}</th><th>{{th_error}}</th><th>{{th_newt_x}}</th><th>{{th_error}}</th></tr></thead>
  <tbody id="rows"></tbody>
</table>
<div class="status" id="status">{{press_step_run}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: 1rem; flex-wrap: wrap; margin: .4rem 0 .7rem; font-size: .88rem; }
.controls label { display: flex; flex-direction: column; gap: .2rem; font-weight: 600; color: #1d3557; }
select { font: 500 13px system-ui, sans-serif; padding: .3rem; border: 1px solid #cdd9e3; border-radius: 6px; background: #fff; }
table.race { border-collapse: collapse; width: 100%; font: 500 13px ui-monospace, monospace; }
table.race th, table.race td { border: 1px solid #cdd9e3; padding: .3rem .5rem; text-align: right; }
table.race th { background: #e8eef3; color: #1d3557; }
table.race td:nth-child(2), table.race td:nth-child(3) { color: #1d4ed8; }
table.race td:nth-child(4), table.race td:nth-child(5) { color: #c92f3c; }
table.race tr.win-n td:nth-child(4) { background: #fde8ea; font-weight: 700; }
table.race tr.win-b td:nth-child(2) { background: #e3ecfb; font-weight: 700; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the asymmetry. Bisection chips away steadily: the error is cut roughly in half every step, so it gains about one decimal digit every three or four iterations — and it always lands. Newton can double the number of correct digits per step, reaching machine precision in a handful of iterations. But start it near a flat spot (a point where the slope is tiny) and the tangent flings it far away — try $x_{0}$ = 0 on the cubic and watch it diverge.

How hard is finding a root, really? For these two methods the answer is completely known — this is settled mathematics, not an open problem.

• Bisection converges linearly. If a continuous function changes sign across [a, b], there must be a root inside (the Intermediate Value Theorem). Halving the interval each step shrinks the error by a factor of 2, so reaching precision ε needs about log₂((b−a)/ε) steps — roughly one binary digit per iteration, guaranteed, no derivative required.
• Newton converges quadratically. Near a simple root, each step roughly squares the error: 2 correct digits become 4, then 8, then 16. Newton (1669) and Joseph Raphson (1690) gave the iteration; the modern convergence proof is classical analysis. The error at step n+1 is bounded by a constant times the square of the error at step n.
• The catch is "near". Newton's speed is only local. Far from the root, or where the derivative is near zero, the tangent step can overshoot wildly, cycle, or diverge — there is no global safety net. Bisection has one and Newton does not.
• So neither dominates. This is a genuine tradeoff, not a bug: guaranteed-but-slow versus fast-but-fragile. The standard fix, Brent's method (1973), blends both — it takes Newton-like steps when they help and falls back to bisection when they don't.

None of this brushes up against the hard limits elsewhere on this site: root-finding for nice functions sits comfortably in P, far from P vs NP. The interesting question here is not "can we?" but "how fast, and how safely?"

"Solve f(x) = 0 numerically" hides inside an enormous amount of everyday computing, and the speed-versus-safety tradeoff shapes every one of them:

• Your calculator. The $\surd$ and 1/x keys, and many library functions, use a couple of Newton steps because doubling-the-digits reaches full precision almost instantly.
• Optimization and machine learning. Setting a derivative to zero is root-finding; Newton's method generalizes to the multivariable solvers and second-order optimizers used to train models, while line searches lean on safe bracketing.
• Graphics and physics engines. Ray–surface intersections and constraint solvers run Newton iterations every frame, with bisection-style fallbacks to stay robust in real time.
• Finance and engineering. Computing a bond's yield, or the operating point of a circuit, means solving a nonlinear equation — fast when it can be, safe when it must be.

The same bracketing idea behind bisection is just binary search on a continuous function — the same halving logic that powers SAT solvers' search and countless sorting and searching routines.

Root-finding is one of the rare corners of this site with a fully happy ending. Bisection is the tortoise that never loses but never hurries; Newton is the hare that sprints to the finish — unless it trips. Both behaviors are proven, quantified, and centuries old.

The deeper lesson outlives the math: speed and safety pull in opposite directions, and the wise engineer takes both. Brent's method and its descendants race like Newton when the going is good and crawl like bisection when it isn't. So the next time a program asks "where does this hit zero?", remember the duel — and remember that the best answer was to stop choosing sides. The same caution shows up wherever fast heuristics meet hard guarantees, including the search at the heart of P vs NP.