# 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