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
- 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?)
- 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
- Modular Multiplication Without Trial Division
- Modular forms, a computational approach. With an appendix by Paul E. Gunnells
- On Schönhage's algorithm and subquadratic integer gcd computation
- On finding primitive roots in finite fields
- SAGE
Cited in
(12)- Lower triangular Toeplitz-Ramanujan systems whose solution yields the Bernoulli numbers
- Irregular primes with respect to Genocchi numbers and Artin's primitive root conjecture
- An alternative to the Euler-Maclaurin summation formula: approximating sums by integrals only
- scientific article; zbMATH DE number 1557041 (Why is no real title available?)
- A subquadratic algorithm for computing the n-th Bernoulli number
- A fast algorithm for computing the number of magic series
- Faster computation of Bernoulli numbers
- 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
- Numerical calculation of the Riemann zeta function at odd-integer arguments: a direct formula method
- Irregular primes to two billion
- Irregular primes to 163 million
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)
