Anomaly in mpn_sqrtrem and mpn_rottrem
nisse at lysator.liu.se
Mon Jun 8 07:27:47 UTC 2015
tg at gmplib.org (Torbjörn Granlund) writes:
> Surely, we could make mpn_rootrem run faster, in particular for small
> arguments. But also for large arguments, 2x slowdown seems like a lot.
I've had a quick look. Both mpn_dc_sqrtrem and mpn_rootrem_internal
(which seem to be the work horses for larger operands) do a division in
the loop. The latter is organized as a newton iteration, the former
isn't (but I guess the computation is more or less equivalent to a
The code is a bit too complex for me to really compare them...
For larger operands, I imagine a rewrite to use a division-free
Newton-iteration for an approximation of the inverse root would be
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel