Anomaly in mpn_sqrtrem and mpn_rootrem

Niels Möller nisse at
Wed Jul 8 21:51:06 UTC 2015

tg at (Torbjörn Granlund) writes:

> But I spotted "% k" and "/ k" there, and those are very expensive,
> unless you table inverses of k, of course...

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.

Precomputing an inverse of k makes sense, if there's more than one
division by k. (I also haven't tried to understand the fine details of
the algorithm).


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list