What is the most efficient known algorithm to calculate Bernoulli Numbers, and what is the time complexity of the algorithm? I'm not too familiar with said time complexity to figure out on my own.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
David Harvey devised a method to efficiently compute $B_n$ modulo $p$ for many small primes $p$, and then reconstructing the original number $B_n$ via the Chinese Remainder Theorem.
In the paper (arXiv:0807.1347v2), Harvey establishes the asymptotic complexity of the algorithm to be $\mathcal O(n^2\log(n)^{2 + \epsilon})$.
There are other methods that exploit the relationship between Bernoulli numbers and the Zeta function, but Harvey's method should be faster since you can easily parallelize it. Harvey computed $B_n$ for $n = 10^8$, a new record. His algorithm is also included in Sage.
