The middle product algorithm I - Speeding up the division and square root of power series
We present new algorithms for the inverse, division, and square root of power series. The key trick is a new algorithm - MiddleProduct or, for short, MP - computing the n middle coefficients of a (2n-1)xn full product in the same number of multiplications as a full nxn product. This improves previous work of Brent, Mulders, Karp and Markstein, Burnikel and Ziegler. These results apply both to series and polynomials.
middle product division square root inversion newton's method