Fast computation of Bernoulli, Tangent and Secant numbers.

Year of edition2011

 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(n^2.(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(n^2) 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).

 16 pages. To appear in Computational and Analytical Mathematics (associated with the May 2011 workshop in honour of Jonathan Borwein's 60th birthday). For further information, see Published at: Springer Proceedings in Mathematics and Statistics, Vol. 50, 2013, 127-142

Reference on publication
Brent R. P., Harvey D. J.  Fast computation of Bernoulli, Tangent and Secant numbers. - : , 2011. //, 2011.
1.Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, Dover, 1973.
2.M. D. Atkinson, How to compute the series expansions of sec x and tan x, Amer. Math. Monthly 93 (1986), 387--389.
3.David H. Bailey, Jonathan M. Borwein and Richard E. Crandall, On the Khintchine constant, Math. Comput. 66 (1997), 417--431.
4.Jonathan M. Borwein and R. M. Corless, Emerging tools for experimental mathematics, Am. Math. Mon. 106 (1999), 899--909.
5.Wieb Bosma, John Cannon and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), 235-???265
6.Richard P. Brent, Unrestricted algorithms for elementary and special functions, in Information Processing 80, North-Holland, Amsterdam, 1980, 613--619. arXiv:1004.3621v1
7.Richard P. Brent and Paul Zimmermann, Modern Computer Arithmetic, Cambridge University Press, 2010, 237 pp. arXiv:1004.4710v1
8.Joe Buhler, Richard Crandall, Reijo Ernvall, Tauno Mets?ankyl?a and M. Amin Shokrollahi, Irregular primes and cyclotomic invariants to twelve million, J. Symbolic Computation 31 (2001), 89--96.
9.Joe Buhler, Richard Crandall, Reijo Ernvall and Tauno Mets?ankyl?a, Irregular primes to four million, Math. Comput. 61 (1993), 151--153.
10.Joe Buhler, Richard Crandall and R. Sompolski, Irregular primes to one million, Math. Comput. 59 (1992), 717--722.
11.Joe Buhler and David Harvey, Irregular primes to 163 million, Math. Comput. 80 (2011), 2435--2444.
12.Thomas Clausen, Theorem, Astron. Nachr. 17 (1840), cols. 351--352.
13.Richard E. Crandall, Topics in Advanced Scientific Computation, SpringerVerlag, 1996.
14.Richard E. Crandall and Carl Pomerance, Prime numbers: A Computational Perspective, Springer-Verlag, 2001.
15.Karl Dilcher and Ilja Sh. Slavutskii, A Bibliography of Bernoulli Numbers (last updated March 3, 2007),
16.Helaman R. P. Ferguson, David H. Bailey and Steve Arno, Analysis of PSLQ, an integer relation finding algorithm, Math. Comput. 68 (1999), 351--369.
17.Martin F?urer, Faster integer multiplication, Proc. 39th Annual ACM Symposium on Theory of Computing (STOC), ACM, San Diego, California, 2007, 57--66.
18.Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, third edition, Addison-Wesley, 1994.
19.Kevin Hare, Multisectioning, Rational Poly-Exponential Functions and Parallel Computation, M.Sc. thesis, Dept. of Mathematics and Statistics, Simon Fraser University, Canada, 2002.
20.David Harvey, A multimodular algorithm for computing Bernoulli numbers, Math. Comput. 79 (2010), 2361--2370.
21.Masanobu Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, J. of Integer Sequences3 (2000). Article 00.2.9, 6 pages.
22.Donald E. Knuth, Euler's constant to 1271 places, Math. Comput. 16 (1962), 275--281.
23.Donald E. Knuth and Thomas J. Buckholtz, Computation of Tangent, Euler, and Bernoulli numbers, Math. Comput. 21 (1967), 663--688.
24.H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341--348.
25.B. F. Logan, unpublished observation, mentioned in [? , ?6.5].
26.Christian Reinsch, personal communication to R. P. Brent, about 1979, acknowledged in [? ].
27.Arnold Sch?onhage and Volker Strassen, Schnelle Multiplikation gro?er Zahlen, Computing 7 (1971), 281--292.
28.Malte Sieveking, An algorithm for division of power series, Computing 10 (1972), 153--156.
29.Neil J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,
30.Karl G. C. von Staudt, Beweis eines Lehrsatzes, die Bernoullischen Zahlen betreffend, J. Reine Angew. Math. 21 (1840), 372--374.
31.Allan Steel, Reduce everything to multiplication, presented at Computing by the Numbers: Algorithms, Precision and Complexity, Workshop for Richard Brent's 60th birthday, Berlin, 2006,
32.William Stein et al, Sage,
33.Edward C. Titchmarsh, The Theory of the Riemann Zeta-Function, second edition (revised by D. R. Heath-Brown), Clarendon Press, Oxford, 1986.

This publication on other resources