Speeding up the Division and Square Root of Power Series (original) (raw)

Rapport (Rapport De Recherche) Année : 2000

Résumé

We present new algorithms for the inverse, quotient, or square root of power series. The key trick is a new algorithm -- RecursiveMiddleProduct or RMP -- computing the nnn middle coefficients of a 2nxn2n x n2nxn product in essentially the same number of operations -- K(n)K(n)K(n) -- than a full nxnn x nnxn product with Karatsuba's method. This improves previous work of Mulders, Karp and Markstein, Burnikel and Ziegler. These results apply both to series, polynomials, and multiple precision floating-point numbers.

Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00072675

Soumis le : mercredi 24 mai 2006-10:33:36

Dernière modification le : mardi 4 novembre 2025-11:58:20

Archivage à long terme le : dimanche 4 avril 2010-23:17:52

Dates et versions

inria-00072675 , version 1 (24-05-2006)

Licence

Identifiants

Citer

Guillaume Hanrot, Michel Quercia, Paul Zimmermann. Speeding up the Division and Square Root of Power Series. [Research Report] RR-3973, INRIA. 2000, pp.20. ⟨inria-00072675⟩

545 Consultations

1119 Téléchargements