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 :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00071921
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:16:27 PM
Last modification on : Thursday, January 11, 2018 - 6:20:00 AM
Long-term archiving on : Sunday, April 4, 2010 - 10:44:37 PM

Identifiers

  • HAL Id : inria-00071921, version 1

Collections

Citation

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

Share

Metrics

Record views

196

Files downloads

1066