The Middle Product Algorithm I | Zendy

Guillaume Hanrot | Zendy; Michel Quercia | Zendy; Paul Zimmermann | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Middle Product Algorithm I

Author(s) -

Guillaume Hanrot,

Michel Quercia,

Paul Zimmermann

Publication year - 2004

Publication title -

applicable algebra in engineering communication and computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.558

H-Index - 35

eISSN - 1432-0622

pISSN - 0938-1279

DOI - 10.1007/s00200-003-0144-2

Subject(s) - algorithm , product (mathematics) , series (stratigraphy) , inverse , computer science , square root , key (lock) , mathematics , arithmetic , division (mathematics) , paleontology , geometry , computer security , biology

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. These results apply both to series and polynomials.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research