Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Faster algorithms for the square root and reciprocal of power series


Author: David Harvey
Journal: Math. Comp. 80 (2011), 387-394
MSC (2010): Primary 68W30
DOI: https://doi.org/10.1090/S0025-5718-2010-02392-0
Published electronically: July 8, 2010
MathSciNet review: 2728985
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We give new algorithms for the computation of square roots and reciprocals of power series in . If $ M(n)$ denotes the cost of multiplying polynomials of degree $ n$, the square root to order $ n$ costs $ (1.333\ldots + o(1)) M(n)$ and the reciprocal costs $ (1.444\ldots + o(1)) M(n)$. These improve on the previous best results, $ (1.8333\ldots + o(1)) M(n)$ and $ (1.5 + o(1)) M(n)$, respectively.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30

Retrieve articles in all journals with MSC (2010): 68W30


Additional Information

David Harvey
Affiliation: Courant Institute of Mathematical Sciences, New York University, 251 Mercer St, New York, New York 10012
Email: dmharvey@cims.nyu.edu

DOI: https://doi.org/10.1090/S0025-5718-2010-02392-0
Received by editor(s): November 10, 2009
Received by editor(s) in revised form: November 25, 2009
Published electronically: July 8, 2010
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.