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:
“The really efficient laborer will be found not to crowd his day with work, but will saunter to his task surrounded by a wide halo of ease and leisure.”
—Henry David Thoreau (1817–1862)
“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 principle of majority rule is the mildest form in which the force of numbers can be exercised. It is a pacific substitute for civil war in which the opposing armies are counted and the victory is awarded to the larger before any blood is shed. Except in the sacred tests of democracy and in the incantations of the orators, we hardly take the trouble to pretend that the rule of the majority is not at bottom a rule of force.”
—Walter Lippmann (1889–1974)