A multimodular algorithm for computing Bernoulli numbers

Math. Comp. 79 (2010), 2361–2370 (DOI).

arXiv preprint (October 2008).

Abstract

We describe an algorithm for computing Bernoulli numbers. Using a parallel implementation, we have computed Bk for k = 108, a new record. Our method is to compute Bk modulo p for many small primes p, and then reconstruct Bk via the Chinese Remainder Theorem. The asymptotic time complexity is O(k2 log2+ε k), matching that of existing algorithms that exploit the relationship between Bk and the Riemann zeta function. Our implementation is significantly faster than several existing implementations of the zeta-function method.

Implementation

I implemented the algorithm described in the paper in the bernmm package.

Data

The 10,000,000-th Bernoulli number

The 31,622,776-th Bernoulli number

The 100,000,000-th Bernoulli number


Back to the main page