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
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

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.