Faster sqrt/root
Torbjorn Granlund
tg at gmplib.org
Wed Aug 3 21:48:12 CEST 2011
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
More information about the gmp-devel
mailing list