A multimodular algorithm for computing Bernoulli numbers
From MaRDI portal
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(k)^(2+epsilon)), 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.
Recommendations
Cites work
- A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm
- An "exact" formula for the m-th Bernoulli number
- Fast multiplication of large numbers
- Faster computation of Bernoulli numbers
- scientific article; zbMATH DE number 45378 (Why is no real title available?)
- scientific article; zbMATH DE number 47996 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 1465050 (Why is no real title available?)
- scientific article; zbMATH DE number 967940 (Why is no real title available?)
- Modular forms, a computational approach. With an appendix by Paul E. Gunnells
- Modular Multiplication Without Trial Division
- On finding primitive roots in finite fields
- On Schönhage's algorithm and subquadratic integer gcd computation
- SAGE
Cited in
(13)- An alternative to the Euler-Maclaurin summation formula: approximating sums by integrals only
- Numerical calculation of the Riemann zeta function at odd-integer arguments: a direct formula method
- A fast algorithm for computing the number of magic series
- Irregular primes with respect to Genocchi numbers and Artin's primitive root conjecture
- Irregular primes to 163 million
- A subquadratic algorithm for computing the n-th Bernoulli number
- scientific article; zbMATH DE number 3851190 (Why is no real title available?)
- The DC algorithm for computing sums of powers of consecutive integers and Bernoulli numbers
- Faster computation of Bernoulli numbers
- scientific article; zbMATH DE number 1557041 (Why is no real title available?)
- Irregular primes to two billion
- Lower triangular Toeplitz-Ramanujan systems whose solution yields the Bernoulli numbers
- Verifying an efficient algorithm for computing Bernoulli numbers
This page was built for publication: A multimodular algorithm for computing Bernoulli numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3160744)
