2-adic roots (Re: bdiv vs redc)
Torbjorn Granlund
tg at gmplib.org
Tue Jul 24 09:22:21 CEST 2012
nisse at lysator.liu.se (Niels Möller) writes:
I think so. I don't fully understand the binv_sqroot, but some
differences:
* As far as I see, it doesn't take any advantage of cancellation in the
iteration.
Except via mpn_powlo and mpn_mullo_n, I suppose.
* It uses powlo in some way which I haven't figured out.
Used for computing x^3 mod B^n.
It is really a very plain Newton iteration being used here.
* And the binv_sqrt function is a lot simpler than mine.
One should note that binv_sqroot is a specialisation of binv_root in the
same file (except that binv_root doesn't make any effort at detecting
failures).
I suppose one should for common k improve the starting value from 1 bit
to a few bits, and for any k iterate in mp_limb_t variables until
getting a full word of precision (using a fully unrolled loop).
--
Torbjörn
More information about the gmp-devel
mailing list