Faster algorithms for the square root and reciprocal of power series
HTML articles powered by AMS MathViewer
- by David Harvey PDF
- Math. Comp. 80 (2011), 387-394 Request permission
Abstract:
We give new algorithms for the computation of square roots and reciprocals of power series in $\mathbf {C}\lBrack x \rBrack$. 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
- Daniel Bernstein, Removing redundancy in high-precision Newton iteration, unpublished, available at http://cr.yp.to/papers.html#fastnewton, 2004.
- Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 325–384. MR 2467550
- Alin Bostan, Grégoire Lecerf, and Éric Schost, Tellegen’s principle into practice, Symbolic and Algebraic Computation (J. R. Sendra, ed.), ACM Press, 2003, Proceedings of ISSAC’03, Philadelphia, August 2003., pp. 37–44.
- Martin Fürer, Faster integer multiplication, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 57–66. MR 2402428, DOI 10.1145/1250790.1250800
- Guillaume Hanrot, Michel Quercia, and Paul Zimmermann, The middle product algorithm. I, Appl. Algebra Engrg. Comm. Comput. 14 (2004), no. 6, 415–438. MR 2042800, DOI 10.1007/s00200-003-0144-2
- Guillaume Hanrot and Paul Zimmermann, Newton iteration revisited, unpublished, available at http://www.loria.fr/˜zimmerma/papers/fastnewton.ps.gz, 2004.
- Arnold Schönhage, Variations on computing reciprocals of power series, Inform. Process. Lett. 74 (2000), no. 1-2, 41–46. MR 1761197, DOI 10.1016/S0020-0190(00)00044-2
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- Joris van der Hoeven, The truncated Fourier transform and applications, ISSAC 2004, ACM, New York, 2004, pp. 290–296. MR 2126956, DOI 10.1145/1005285.1005327
- —, Notes on the truncated Fourier transform, unpublished, available from http://www.math.u-psud.fr/˜vdhoeven/, 2005.
- —, Newton’s method and FFT trading, preprint available at http://hal.archives-ouvertes.fr/hal-00434307/, 2009.
Additional Information
- David Harvey
- Affiliation: Courant Institute of Mathematical Sciences, New York University, 251 Mercer St, New York, New York 10012
- MR Author ID: 734771
- ORCID: 0000-0002-4933-658X
- Email: dmharvey@cims.nyu.edu
- Received by editor(s): November 10, 2009
- Received by editor(s) in revised form: November 25, 2009
- Published electronically: July 8, 2010
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 80 (2011), 387-394
- MSC (2010): Primary 68W30
- DOI: https://doi.org/10.1090/S0025-5718-2010-02392-0
- MathSciNet review: 2728985