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
  * As far as I see, it doesn't take any advantage of cancellation in the
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

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).


More information about the gmp-devel mailing list