Once a root is sufficiently isolated by bisection and narrowing, a faster numerical method can be applied to obtain remaining digits of the root.  Newton's method, the secant method, Muller's algorithm, third-order Newton iteration, and quadratic inverse interpolation all have superlinear convergence and are described in Rice[13].  We use Newton's method because it is well-known, is efficient, has low-overhead, and is easy to analyze. 

Given function , define function by

If is a root of on , then .  Hence is a fixed point of .  Newton's method for calculating root of starts with an approximation and then successively computes .  Under the right conditions, explained below, the sequence , , , converges to . 

Formulas for the derivatives of are:

Letting and using and we obtain via Taylor series expansions the results

for some .  If and for all and for all , then Newton's method is safe to use and converges faster than bisection if either

and we can guarantee that all .  The latter can be arranged by tweaking Newton's method so that if overshoots the boundaries of interval , then is shoved back towards the root .  Subsequent computed by then proceeds without incident.  Hence, we use

Now we assume 's continuity property extends to derivatives of on subinterval .  If interval is sufficiently small, then and will determine finite bounds and . 

We modify procedure Locate and introduce procedures NewtonTest and Newton.  Procedure NewtonTest tests whether Newton's method should be used and procedure Newton actually implements Newton's method.  These are listed below.

proc Locate
if and then
return ;
else
for from do
;
if
and NewtonTest then
;
break;
elif
and then
break;
elif then
;
else
;
fi;
od;
return ;
fi;

proc NewtonTest
global ;
if CouldBeZero then
return false;
else
;
;
;
;
if and then
return false;
else
;
;
if and then
return false;
else
return true;
fi;
fi;
fi;

proc Newton
global ;
;
;
;
while and do
;
;
od;
while do
;
;
od;
return ;

is another "fudge factor" which in our algorithm is currently set to the value .