Faster sqrt/root

[Torbjorn Granlund]

In a typical sqrt(A) Newton iteration, ere is a division A/x_k where x_k
is the kth approximation.  If A is 2n bits, x_k is about n bits.

Division of a 2n-bit number by an n-bit number is typically about 2x
slower than a n-bit by n-bit multiplication.

Perhaps one could save the quotient from A/x_{k-1}, call it q_{k-1}, and
compute A/x_k by first computing A-(x_k * q_{k-1}), then develop further
quotient bits starting with this partial remainder?

If I am not mistaken, this will save about half the division time,
resulting in perhaps a 25% speedup.

-- 
Torbjörn