2009/10/10 by Harvey, David
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.0910.1926
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 root to order n costs (1.333... + o(1)) M(n) and the reciprocal costs (1.444... + o(1)) M(n). These improve on the previous best results, respectively (1.8333... + o(1)) M(n) and (1.5 + o(1)) M(n).