square root and reciprocal

[David Harvey]

Dear developers,

I would like to draw attention to my preprint "Faster algorithms for  
the square root and reciprocal of power series":

http://arxiv.org/abs/0910.1926

For power series over the complex numbers, one can compute

* square root to order n in time (1.333 + o(1)) M(n), and with  
remainder in time (1.666 + o(1)) M(n)
* reciprocal to order n in time (1.444 + o(1)) M(n)

where M(n) is the time for multiplying polynomials of degree n.

I expect that these algorithms can be adapted to the arbitrary- 
precision integer case. The algorithms would be particularly relevant  
for GMP if GMP switches from Schonhage-Strassen to a small-prime FFT  
(number-theoretic transform) multiplication algorithm, which has been  
been discussed recently on this list.

I don't have time to work on an implementation in GMP right now, but  
if anyone decides to sink some time into it, I would be interested to  
hear about the results.

david