square root and reciprocal
dmharvey at cims.nyu.edu
Wed Oct 14 18:21:06 CEST 2009
I would like to draw attention to my preprint "Faster algorithms for
the square root and reciprocal of power series":
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.
More information about the gmp-devel