Newton's method doubles the correct digits

Adam Zettel · September 24, 2026 · written with an agent

e_{n + 1} \approx \frac{e _{n}^{2}}{2 2}

Newton's method on $x^{2} = 2$ , one cell at a time. From $x_{0} = 1$ the error is $1.6 \times 1 0^{- 12}$ after four steps and zero after five; bisection needs 39 halvings to promise as much. Each Newton step squares the error, and a cell checks the constant in front.

Open in the workbench Download .vivOutputs below are from the site build’s run; Run all runs it again in your browser.

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

A notebook: the prose between the cells says what each one is for, and each cell's output appears under it. Press Run all, or run a cell with Shift+Enter.

Printed

x1: 1.5

One step

The tangent to $f (x) = x^{2} - 2$ at $x = 1$ has slope $f^{'} (1) = 2$ and passes through $(1, - 1)$ . It crosses zero at $x = 1 - (- 1) /2 = 1.5$ , which is what the cell above printed. Already $1. 5^{2} = 2.25$ is close to 2.

Before running the next cell, guess how many steps it takes to get every digit a double can hold, about 16.

Printed

xs: [1, 1.5, 1.41667, 1.41422, 1.41421, 1.41421]

errs: [0.414214, 0.0857864, 0.0024531, 2.1239e-06, 1.59472e-12, 0]

Tests 3 of 3 pass

after four steps the error is below 2e-12 (passes)
after five steps the error is zero: x is sqrt(2) to the last bit (passes)
a double holds about 16 decimal digits: 53 bits, 15.95 digits (passes)

Why the digits double

Write the error as $e_{n} = x_{n} - 2$ . One step gives

x_{n + 1} - 2 = x_{n} - \frac{x _{n}^{2} - 2}{2 x _{n}} - 2 = \frac{( x _{n} - 2 ) ^{2}}{2 x _{n}},

so $e_{n + 1} = e_{n}^{2} / (2 x_{n})$ . Near the root $x_{n} \approx 2$ , and the error is squared at every step and scaled by $1/ (22) \approx 0.354$ . An error of $1 0^{- 3}$ becomes $3.5 \times 1 0^{- 7}$ , then $4.4 \times 1 0^{- 14}$ : the number of correct digits doubles.

The cell below measures $e_{n + 1} / e_{n}^{2}$ for the first four steps. Far from the root the ratio is $1/ (2 x_{n})$ with $x_{n}$ still far from $2$ ; by the fourth step it matches $1/ (22)$ to four digits.

Printed

ratio: 0.5

ratio: 0.333333

ratio: 0.352941

ratio: 0.353522

Tests 3 of 3 pass

an error of 1e-3 becomes 3.5e-7, then 4.4e-14 (passes)
the first ratio is 1 / (2 x_0) = 1/2, exactly as the algebra says (passes)
by the fourth step e_(n+1) / e_n^2 is 1 / (2 sqrt 2) to four digits (passes)

Against bisection

Bisection keeps an interval where $f$ changes sign and halves it. After $k$ halvings of $[1, 2]$ the midpoint is within $2^{- (k + 1)}$ of the root, one binary digit per step, and that guarantee is all it has: it never fails, and it never speeds up. The figure plots $lo g_{10}$ of Newton's error beside $lo g_{10}$ of bisection's guarantee. Newton's curve bends down; bisection's is a straight line.

Printed

match: 39

bisection, half the interval

Tests 1 of 1 pass

bisection needs 39 halvings to promise what four Newton steps did (passes)