Faster algorithms for the square root and reciprocal of power series

David Harvey

We give new algorithms for the computation of square roots and reciprocals of power series in C[[x]]. If M(n) denotes the cost of multiplying polynomials of degree n, the square ro…