Skip to Main content Skip to Navigation

The Middle Product Algorithm, I.

Guillaume Hanrot 1 Michel Quercia Paul Zimmermann 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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)*n full product in the same number of multiplications as a full n*n product. This improves previous work of Brent, Mulders, Karp and Markstein, Burnikel and Ziegler. A forthcoming paper will study the floating-point case.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:16:27 PM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:44:37 PM


  • HAL Id : inria-00071921, version 1



Guillaume Hanrot, Michel Quercia, Paul Zimmermann. The Middle Product Algorithm, I.. [Research Report] RR-4664, INRIA. 2002. ⟨inria-00071921⟩



Record views


Files downloads