Newton's Method

Find a root of $f$ by repeatedly following the tangent line:

$x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )} .$

Quadratic convergence — the number of correct digits roughly doubles each step, so ~6 iterations take you from 1 to 64 correct bits.

double newton(function<double(double)> f, function<double(double)> df, double x0) {
    double x = x0;
    for (int it = 0; it < 100; it++) {
        double fx = f(x);
        if (fabs(fx) < 1e-15) break;
        x -= fx / df(x);
    }
    return x;
}

Integer square root — the practical case

long long isqrt(long long n) {
    if (n < 0) return -1;
    long long x = (long long)sqrtl((long double)n);   // good initial guess
    while (x * x > n) x--;                             // correct for rounding
    while ((x + 1) * (x + 1) <= n) x++;
    return x;
}

Always correct the result of sqrt. sqrt(n) on a double is inexact for $n$ near $1 0^{18}$ and returns a value off by one surprisingly often — a classic source of wrong answers. The two adjustment loops cost nothing and make it exact.

The same pattern works for integer $k$ -th roots:

long long iroot(long long n, int k) {
    long long x = (long long)powl((long double)n, 1.0L / k);
    while (ipow(x + 1, k) <= n) x++;
    while (x > 0 && ipow(x, k) > n) x--;
    return x;
}

Convergence and its failures

Newton converges quadratically near a simple root with $f^{'} \neq = 0$ . It fails when:

Failure	Symptom	Fix
$f^{'} (x_{n}) \approx 0$	huge jump, divergence	bisection fallback
Bad starting point	converges to a different root, or diverges	bracket first
Multiple root ( $f^{'} = 0$ at the root)	linear, not quadratic, convergence	use $x - m f / f^{'}$ for multiplicity $m$
Oscillation	cycles between two points	damping, or a hybrid method

The robust choice is a hybrid: maintain a bracketing interval, take a Newton step, and fall back to bisection whenever the step leaves the bracket. That is what Brent's method does, and it guarantees convergence while keeping Newton’s speed.

For contest purposes, binary search with a fixed iteration count is usually the right call: slower per step, but unconditionally correct and impossible to get wrong.

Newton beyond real numbers

The same iteration $x \leftarrow x - f (x) / f^{'} (x)$ works in any setting with the right notion of “derivative”, and each application doubles the precision:

Setting	Iteration	Doubles
Reals	$x - f / f^{'}$	correct digits
Power series inverse	$B \leftarrow B (2 - A B)$	correct coefficients
Power series , $lo g$ , $exp$	analogous	coefficients
$p$-adic (Hensel lifting)	$r - f (r) f^{'} (r)^{- 1}$	the power of $p$
Matrix inverse	$X (2 I - A X)$	correct digits
Big-integer reciprocal	$x (2 - a x)$	bits — this is how division is implemented

Recognising Newton in all of these is genuinely useful: it turns “how do I compute the inverse of a power series in $O (n lo g n)$ ?” into a solved problem.

Because the cost of the last doubling step dominates, the total is $T (n) = T (n /2) + O (M (n)) = O (M (n))$ — the same as a single multiplication.

Other root-finding methods

Method	Convergence	Needs $f^{'}$
Bisection	linear (1 bit/step)	no — always works
Newton	quadratic	yes
Secant	superlinear ( $ϕ \approx 1.618$ )	no
Regula falsi	linear to superlinear	no
Brent	superlinear, guaranteed	no
Fixed-point iteration	depends on the map	no

The secant method replaces $f^{'}$ with a finite difference — useful when the derivative is unavailable, at a modest cost in convergence rate.

Optimisation via Newton

Applying Newton to $f^{'}$ finds a stationary point:
$x_{n + 1} = x_{n} - \frac{f ^{'} ( x _{n} )}{f ^{''} ( x _{n} )} .$
Quadratically convergent, but it finds any critical point, not necessarily a minimum. Ternary search is safer for unimodal functions in a contest.

See also: Binary Search · Formal Power Series · Hensel Lifting

whoashish's cp notes

Directory