A subquadratic algorithm for computing the $n$-th Bernoulli number
HTML articles powered by AMS MathViewer
- by David Harvey PDF
- Math. Comp. 83 (2014), 2471-2477
Abstract:
We describe a new algorithm that computes the $n$th Bernoulli number in $n^{4/3 + o(1)}$ bit operations. This improves on previous algorithms that had complexity $n^{2 + o(1)}$.References
- Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput. 36 (2007), no. 6, 1777–1806. MR 2299425, DOI 10.1137/S0097539704443793
- Richard P. Brent and David Harvey, Fast computation of Bernoulli, Tangent and Secant numbers, in Proceedings of a Workshop on Computational and Analytical Mathematics in honour of Jonathan Borwein’s 60th birthday, Springer Proceedings in Mathematics, Vol. 50, 2013, 127–142, http://dx.doi.org/10.1007/978-1-4614-7621-4_8.
- Henri Cohen, Number theory. Vol. II. Analytic and modern tools, Graduate Texts in Mathematics, vol. 240, Springer, New York, 2007. MR 2312338
- Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR 0460128
- David Harvey, A multimodular algorithm for computing Bernoulli numbers, Math. Comp. 79 (2010), no. 272, 2361–2370. MR 2684369, DOI 10.1090/S0025-5718-2010-02367-1
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
- Victor Shoup, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (New York, NY, USA), ISSAC ’91, ACM, 1991, pp. 14–21.
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
- Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
Additional Information
- David Harvey
- Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
- MR Author ID: 734771
- ORCID: 0000-0002-4933-658X
- Email: d.harvey@unsw.edu.au
- Received by editor(s): October 14, 2012
- Received by editor(s) in revised form: February 7, 2013
- Published electronically: April 1, 2014
- Additional Notes: The author was supported by the Australian Research Council, DECRA Grant DE120101293.
- © Copyright 2014 David Harvey
- Journal: Math. Comp. 83 (2014), 2471-2477
- MSC (2010): Primary 11B68, 11Y55
- DOI: https://doi.org/10.1090/S0025-5718-2014-02832-9
- MathSciNet review: 3223342