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