Fast Computation of Bernoulli, Tangent and Secant Numbers
242. R. P. Brent and D. Harvey,
Fast computation of Bernoulli, Tangent and Secant numbers,
Proceedings of a Workshop on Computational and Analytical
Mathematics in honour of Jonathan Borwein's 60th birthday,
Springer Proceedings in Mathematics and Statistics, Vol. 50, 2013, 127-142.
arXiv:1108.0286v3
Preprint:
pdf (152K).
Abstract
We consider the computation of Bernoulli, Tangent (zag), and Secant (zig or
Euler) numbers. In particular, we give asymptotically fast algorithms for
computing the first n such numbers in
O(n2(log n)2+o(1)) bit-operations.
We also give very short in-place algorithms for computing the first
n Tangent or Secant numbers in O(n2) integer
operations. These algorithms are extremely simple, and fast for moderate
values of n.
They are faster and use less space than the algorithms of Atkinson (for
Tangent and Secant numbers) and Akiyama and Tanigawa (for Bernoulli
numbers).
Notes
The version arXiv:1108.0286v1 did not include the comparison with
Atkinson's algorithm. Thanks to Christopher Heckman for drawing our
attention to Atkinson's 1986 paper. Version v2 mentions Atkinson's paper
and version v3 includes some additional references and acknowledgements.
The original reference for the algorithm of Akiyama and Tanigawa is:
S. Akiyama and Y. Tanigawa, Multiple zeta values at non-positive integers,
The Ramanujan Journal 5 (2001), 327-351.
An interesting O(n2) algorithm for computing Bernoulli
numbers was published as early as 1877 by P. L. von Seidel
[Uber eine einfache Entstehungsweise der Bernoullischen Zahlen und
einiger verwandten Reihen, Sitzungsber. Munch. Akad.
4 (1877), 157-187].
A description can be found on the Wikipedia page
for
Bernoulli numbers.
We were not aware of Seidel's algorithm when writing our paper.
Return to Richard Brent's index page