Faster algorithms for the square root and reciprocal of power series

Math. Comp. 80 (2011), 387–394 (DOI).

arXiv preprint (October 2009).

Abstract

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).

Postscript

It has been brought to the author's attention that Igor Sergeev found better constants in 2007. He obtains complexity (1.25 + o(1)) M(n) for both the reciprocal and square root, in a similar FFT model (Proc. IX International Conf. “Discrete mathematics and its applications”, Moscow State University, 123–126, in Russian). However, Sergeev's method requires considering products of three Fourier transforms, and appears unlikely to achieve the same constants in a synthetic FFT model (Sergeev, personal communication). It is unclear whether it can achieve the same constants in the integer or floating-point setting.


Back to the main page