Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

A multimodular algorithm for computing Bernoulli numbers


Author: David Harvey
Journal: Math. Comp. 79 (2010), 2361-2370
MSC (2010): Primary 11B68; Secondary 11Y60
DOI: https://doi.org/10.1090/S0025-5718-2010-02367-1
Published electronically: June 2, 2010
MathSciNet review: 2684369
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We describe an algorithm for computing Bernoulli numbers. Using a parallel implementation, we have computed $ B_k$ for $ k = 10^8$, a new record. Our method is to compute $ B_k$ modulo $ p$ for many small primes $ p$ and then reconstruct $ B_k$ via the Chinese Remainder Theorem. The asymptotic time complexity is $ O(k^2 \log^{2+\varepsilon} k)$, matching that of existing algorithms that exploit the relationship between $ B_k$ and the Riemann zeta function. Our implementation is significantly faster than several existing implementations of the zeta-function method.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11B68, 11Y60

Retrieve articles in all journals with MSC (2010): 11B68, 11Y60


Additional Information

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

DOI: https://doi.org/10.1090/S0025-5718-2010-02367-1
Received by editor(s): November 17, 2008
Published electronically: June 2, 2010
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.