Efficient Computation of Bernoulli Numbers
In some applications it is useful to be able to compute the Bernoulli numbers B0 through Bp − 3 modulo p, where p is a prime; for example to test whether Vandiver's conjecture holds for p, or even just to determine whether p is an irregular prime. It is not feasible to carry out such a computation using the above recursive formulae, since at least (a constant multiple of) p2 arithmetic operations would be required. Fortunately, faster methods have been developed (Buhler et al. 2001) which require only O(p (log p)2) operations (see big-O notation).
David Harvey (Harvey 2008) describes an algorithm for computing Bernoulli numbers by computing Bn modulo p for many small primes p, and then reconstructing Bn via the Chinese Remainder Theorem. Harvey writes that the asymptotic time complexity of this algorithm is O(n2 log(n)2+eps) and claims that this implementation is significantly faster than implementations based on other methods. Using this implementation Harvey computed Bn for n = 108. Harvey's implementation is included in Sage since version 3.1. Pavel Holoborodko (Holoborodko 2012) computed Bn for n = 2*108 using Harvey's implementation, which is a new record. Prior to that Bernd Kellner (Kellner 2002) computed Bn to full precision for n = 106 in December 2002 and Oleksandr Pavlyk (Pavlyk 2008) for n = 107 with 'Mathematica' in April 2008.
-
Computer Year n Digits* J. Bernoulli ~1689 10 1 L. Euler 1748 30 8 J.C. Adams 1878 62 36 D.E. Knuth, T.J. Buckholtz 1967 1672 3330 G. Fee, S. Plouffe 1996 10000 27677 G. Fee, S. Plouffe 1996 100000 376755 B.C. Kellner 2002 1000000 4767529 O. Pavlyk 2008 10000000 57675260 D. Harvey 2008 100000000 676752569 P. Holoborodko 2012 200000000
- Digits is to be understood as the exponent of 10 when B(n) is written as a real in normalized scientific notation.
Read more about this topic: Bernoulli Number
Famous quotes containing the words efficient, computation and/or numbers:
“I make no secret of the fact that I would rather lie on a sofa than sweep beneath it. But you have to be efficient if you’re going to be lazy.”
—Shirley Conran (b. 1932)
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“The forward Youth that would appear
Must now forsake his Muses dear,
Nor in the Shadows sing
His Numbers languishing.”
—Andrew Marvell (1621–1678)