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).


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).


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