Editing Bernoulli number (section)

== Efficient computation of Bernoulli numbers ==

In some applications it is useful to be able to compute the Bernoulli numbers {{math|''B''<sub>0</sub>}} through {{math|''B''<sub>''p'' − 3</sub>}} modulo {{mvar|p}}, where {{mvar|p}} is a prime; for example to test whether [[Vandiver's conjecture]] holds for {{mvar|p}}, or even just to determine whether {{mvar|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) {{math|''p''<sup>2</sup>}} arithmetic operations would be required. Fortunately, faster methods have been developed{{r|BuhlerCraErnMetShokrollahi2001}} which require only {{math|''O''(''p'' (log ''p'')<sup>2</sup>)}} operations (see [[big-O notation|big {{mvar|O}} notation]]).

David Harvey{{r|Harvey2010}} describes an algorithm for computing Bernoulli numbers by computing {{math|''B''<sub>''n''</sub>}} modulo {{mvar|p}} for many small primes {{mvar|p}}, and then reconstructing {{math|''B''<sub>''n''</sub>}} via the [[Chinese remainder theorem]]. Harvey writes that the [[Asymptotic analysis|asymptotic]] [[Computational complexity theory|time complexity]] of this algorithm is {{math|''O''(''n''<sup>2</sup> log(''n'')<sup>2 + ''ε''</sup>)}} and claims that this [[implementation]] is significantly faster than implementations based on other methods. Using this implementation Harvey computed {{math|''B''<sub>''n''</sub>}} for {{math|''n'' {{=}} 10<sup>8</sup>}}. Harvey's implementation has been included in [[SageMath]] since version 3.1. Prior to that, Bernd Kellner{{r|Kellner2002}}<!--A more specific citation would be preferable.--> computed {{math|''B''<sub>''n''</sub>}} to full precision for {{math|''n'' {{=}} 10<sup>6</sup>}} in December 2002 and Oleksandr Pavlyk{{r|Pavlyk29Apr2008}} for {{math|''n'' {{=}} 10<sup>7</sup>}} with [[Mathematica]] in April 2008.

{{table alignment}}
:{| class="wikitable defaultright col1left"
! 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 || {{val|1672|fmt=gaps}} || {{val|3330|fmt=gaps}}
|- 
| G. Fee, [[S. Plouffe]] || 1996 || {{val|10000}} || {{val|27677}}
|- 
| G. Fee, S. Plouffe || 1996 || {{val|100000}} || {{val|376755}}
|- 
| B. C. Kellner || 2002 || {{val|1000000}} || {{val|4767529}}
|- 
| O. Pavlyk || 2008 || {{val|10000000}} || {{val|57675260}}
|- 
| D. Harvey || 2008 || {{val|100000000}} || {{val|676752569}}
|}
::<nowiki>*</nowiki> ''Digits'' is to be understood as the exponent of 10 when {{math|''B''<sub>''n''</sub>}} is written as a real number in normalized [[scientific notation]].