2-adic roots (Re: bdiv vs redc)

[Torbjorn Granlund]

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