Faster algorithms for the square root and reciprocal of power series
David Harvey · Mathematics of Computation · 2010
We give new algorithms for the computation of square roots and reciprocals of power series in \mathbf {C}\lBrack x \rBrack . If M ( n ) M(n) denotes the cost of multiplying polynomials of degree n n , the square root to order n n costs ( 1.333 … + o ( 1 ) ) M ( n ) (1.333\ldots + o(1)) M(n) and the reciprocal costs ( 1.444 … + o ( 1 ) ) M ( n ) (1.444\ldots + o(1)) M(n) . These improve on the previous best results, ( 1.8333 … + o ( 1 ) ) M ( n ) (1.8333\ldots + o(1)) M(n) and ( 1.5 + o ( 1 ) ) M ( n ) (1.5 + o(1)) M(n) , respectively.