Anomaly in mpn_sqrtrem and mpn_rootrem
tg at gmplib.org
Wed Jul 8 21:57:48 UTC 2015
nisse at lysator.liu.se (Niels Möller) writes:
There are divisions also in the newton iteration, right? Then a single
division in the computation of the initial value is likely a win, if it
saves two or more iterations in the loop.
There are GMP division operations, but these are not likely going to hit
any hardware division.
Precomputing an inverse of k makes sense, if there's more than one
division by k.
I think we should consider using special starting approximations for
important k, and then perhaps this general 5-bit code for the remaining
Surely the most important k is 3 (assuming 2 is always handled by the
sqrt code). We could provide a 8-bit table here which just performs
masking and indexing. Some other small k values might deserve such
Please encrypt, key id 0xC8601622
More information about the gmp-devel