FLINT3.7.0-dev
Algorithm

Bernoulli numbers

Cost
O(n2log⁡O(1)n)O(n^2 \log^{O(1)} n) bit operations for an isolated BnB_n by either the zeta or the multimodular method; O(n3)O(n^3) with a small constant for all of B0,…,BnB_0, \ldots, B_n with the reverse iterator.

The Bernoulli numbers BnB_n are the rational numbers defined by x/(ex−1)=∑n≥0Bnxn/n!x/(e^x - 1) = \sum_{n \ge 0} B_n x^n/n!. They vanish for odd n≥3n \ge 3, alternate in sign for even nn, and grow quickly:

B2m=(−1)m+12 (2m)!(2π)2mζ(2m),log⁡2∣Bn∣=nlog⁡2n2πe+O(log⁡n).B_{2m} = (-1)^{m+1} \frac{2\, (2m)!}{(2\pi)^{2m}} \zeta(2m), \qquad \log_2 |B_n| = n \log_2 \frac{n}{2\pi e} + O(\log n).

The numerator of BnB_n thus has about nlog⁡2nn \log_2 n bits; that of B106B_{10^6} has about 15.8 million. For the classical theory see [IR1990, Chapter 15] and [Coh2007b, Chapter 9].

The denominator#

Theorem 1 (von Staudt–Clausen). For even n≥2n \ge 2,

Bn+∑(p−1)∣n1p∈Z,B_n + \sum_{(p - 1) \mid n} \frac{1}{p} \in \mathbb{Z},

the sum running over the primes pp with (p−1)∣n(p - 1) \mid n. In particular the denominator of BnB_n in lowest terms is ∏(p−1)∣np\prod_{(p-1) \mid n} p, squarefree and divisible by 6.

The denominator is therefore found from the divisors of nn (arith_bernoulli_number_denom tests the primes up to n+1n + 1, with a table for n≤178n \le 178). It is small: at most ∏d∣n(d+1)\prod_{d \mid n} (d + 1), so it has at most σ0(n)log⁡2(n+1)\sigma_0(n) \log_2(n+1) bits, and usually far fewer. All methods below therefore compute the numerator Nn=dnBnN_n = d_n B_n, an integer.

The zeta function method#

Since dnd_n is known, it suffices to compute BnB_n numerically with an absolute error below 1/(2dn)1/(2 d_n), that is, to about log⁡2∣Bn∣+log⁡2dn+1\log_2 |B_n| + \log_2 d_n + 1 significant bits. With pp bits of precision, the formula above needs n!n! and πn\pi^n (cheap: binary splitting and a power) and ζ(n)\zeta(n), which is 1+O(2−n)1 + O(2^{-n}) and for which very few terms are needed:

ζ(n)=∑j=1Jj−n+ϵ,0<ϵ<∫J∞t−n dt<J1−n,\zeta(n) = \sum_{j=1}^{J} j^{-n} + \epsilon, \qquad 0 < \epsilon < \int_J^\infty t^{-n}\, dt < J^{1-n},

so J≈2p/(n−1)J \approx 2^{p/(n-1)} terms suffice, which is O(n/log⁡n)O(n/\log n) for p≈nlog⁡2np \approx n \log_2 n. Equivalently one evaluates the Euler product ζ(n)−1=∏q≤J(1−q−n)\zeta(n)^{-1} = \prod_{q \le J} (1 - q^{-n}) over primes, with O(n/log⁡2n)O(n/\log^2 n) factors. FLINT's arb_bernoulli_ui_zeta uses the Euler product when nn is small compared with the precision and an asymptotic expansion of ζ(n)\zeta(n) otherwise, in ball arithmetic. _bernoulli_fmpq_ui_zeta multiplies the ball by dnd_n and returns the unique integer it contains (increasing the precision in the unlikely event that the ball contains two). Each power q−nq^{-n} costs O(M(nlog⁡n)log⁡n)O(M(n \log n) \log n), so the total is O(nM(nlog⁡n))O(n M(n \log n)), about n2log⁡2+o(1)nn^2 \log^{2+o(1)} n bit operations.

The reverse iterator#

To compute all of B0,B2,…,BnB_0, B_2, \ldots, B_n, evaluating each from scratch would cost n3n^3. Bloemen's observation [Blo2009] is that the power table can be shared: if the powers j−nj^{-n} are stored in fixed point with pp fractional bits, then j−(n−2)=j−n⋅j2j^{-(n-2)} = j^{-n} \cdot j^2 is one multiplication by a word. Going down in nn thus updates the table with cheap exact multiplications (going up would need divisions), and the precision and the number of terms needed decrease along the way.

Algorithm 1: Reverse iteration

Input: an even nmax⁡n_{\max}.

Output: Bnmax⁡,Bnmax⁡−2,…,B0B_{n_{\max}}, B_{n_{\max} - 2}, \ldots, B_0.

  1. Choose the precision pp from the size of Bnmax⁡B_{n_{\max}} and of its denominator, and J≈2(p+1)/(nmax⁡−1)J \approx 2^{(p+1)/(n_{\max} - 1)}.
  2. For odd j=3,5,…,Jj = 3, 5, \ldots, J compute Pj=⌊2pj−nmax⁡⌋P_j = \lfloor 2^p j^{-n_{\max}} \rfloor with a bound on the rounding error. Compute F=2 nmax⁡!/(2π)nmax⁡F = 2\, n_{\max}! / (2\pi)^{n_{\max}}.
  3. For n=nmax⁡,nmax⁡−2,…n = n_{\max}, n_{\max} - 2, \ldots:

    1. S=2−p∑jPjS = 2^{-p} \sum_j P_j encloses ∑j≥3 oddj−n\sum_{j \ge 3 \text{ odd}} j^{-n} up to the accumulated rounding errors and the tail of the series.
    2. δ=ζ(n)−1=S+(1+S)/(2n−1)\delta = \zeta(n) - 1 = S + (1 + S)/(2^n - 1); Bn=±F(1+δ)B_n = \pm F (1 + \delta); round dnBnd_n B_n to the integer, if the error bound allows it.
    3. Update Pj←j2PjP_j \gets j^2 P_j, F←F(2π)2/(n(n−1))F \gets F (2\pi)^2 / (n(n-1)).
    4. Now and then, lower pp and JJ to the values needed for the current nn, truncating the PjP_j.

Each step costs O(J)O(J) multiplications of a pp-bit number by a word, O(n/log⁡n⋅nlog⁡n)=O(n2)O(n/\log n \cdot n \log n) = O(n^2) bit operations, plus two multiplications of pp-bit numbers, so all the even Bernoulli numbers up to nn cost O(n3)O(n^3) in the worst case but with a very small constant.

FLINT's implementation (bernoulli_rev_init, bernoulli_rev_next) organizes this as follows.

  • Batches. The numbers are produced in batches of k=16k = 16 consecutive indices (k=8k = 8 below n=4000n = 4000) and yielded from a buffer. Step 3.1 for the whole batch is one pass over the table: for each jj, the kk multiplications by j2j^2 and the kk additions into the sums are done while the number PjP_j is in cache. The frame pp and the number of terms JJ are lowered at every batch.
  • The table. With AVX-512 IFMA, the PjP_j are stored as digits of 50 bits (redundant, below 2512^{51}) in 64-bit lanes, multiplied by j2j^2 with vpmadd52luq/vpmadd52huq and summed without carries, the digit sums being converted to limbs every 4096 powers; this needs j<224j < 2^{24}. Otherwise the table is in limbs, updated by mpn_mul_1 and summed by mpn_add_n directly into the accumulators, eight powers at a time by blocks of 256 limbs (the carries of the products between blocks being kept), so that a block of a power is stepped kk times while in cache and the blocks of the kk sums serve all eight powers; streaming each power and the kk sums kk times over is bound by the memory bandwidth once the powers exceed the L2 cache (half the speed for powers of 2⋅1052 \cdot 10^5 limbs on one thread). In step 2 the powers of the primes are computed by powering in ball arithmetic and those of the composites j=abj = ab (aa the smallest prime factor) as ⌊PaPb/2p⌋\lfloor P_a P_b / 2^p \rfloor from the top limbs of the entries of aa and bb, so that nothing beyond the table is held; the primes, and then the composites in [L,3L)[L, 3L) for L=9,27,…L = 9, 27, \ldots (whose cofactors are below LL), are done in parallel. The table takes about ∑j≤J(p−nlog⁡2j)≈n2/24\sum_{j \le J} (p - n \log_2 j) \approx n^2/24 bits; it shrinks as nn decreases (the frame is lowered by about 2log⁡2(n/2π)2 \log_2(n/2\pi) bits per step while PjP_j grows by 2log⁡2j2 \log_2 j bits, j≤J≈n/(2πe)j \le J \approx n/(2\pi e)), and a buffer is reallocated when it is more than about 1/8 empty.
  • The sieve. For n≥105n \ge 10^5, the table only holds the jj prime to 33 and 55 and, apart, the {3,5}\{3,5\}-smooth jj (3, 5, 9, 15, 25, ..., a few dozen): by unique factorization 1+∑j≥3 oddj−n=(1+G)(1+S)1 + \sum_{j \ge 3 \text{ odd}} j^{-n} = (1 + G)(1 + S) with GG and SS the sums over the smooth and the prime-to-15 j≤Jj \le J, up to terms j−nj^{-n} with distinct odd j>Jj > J, which the tail bound covers. This costs one product GSGS per number, of the size of 15−n15^{-n} in the frame, and removes 1−(2/3)(4/5)=7/151 - (2/3)(4/5) = 7/15 of the jj and about as much of the table (more of the small jj, which hold the most limbs, are removed than of the large ones), saving more in the table pass than the product costs at these sizes. The smooth powers stay in limbs (with digits, their frame is lowered by shifts) and are summed by one task of the pass.
  • The products. FF is a floating-point number of W≈p/64+2W \approx p/64 + 2 limbs. The two products of a step, F(2π)2F (2\pi)^2 and FδF \delta, both only need the high half: δ\delta is aligned so that both read the window of limbs [W−1,2W)[W - 1, 2W) of a product of WW-limb operands, and with fft_small the forward transform of FF is shared by the two products and that of (2π)2(2\pi)^2 is cached, so that a step costs four transforms. WW is lowered in steps of about 3%, so that the transform plan serves many batches. The division by 2n−12^n - 1 in step 3.2 is done in linear time, by summing the nn-bit chunks of the dividend from the top.
  • Rounding. All the error terms are tracked, and the fraction of dnF(1+δ)d_n F (1 + \delta) must stay away from 1/21/2 by more than the error bound; otherwise (which is not expected to happen) BnB_n is computed by _bernoulli_fmpq_ui.
  • Threads. The numbers of a batch become independent if the prefactors are obtained as Fn0−2t=Fn0(2π)2t/(n0(n0−1)⋯(n0−2t+1))F_{n_0 - 2t} = F_{n_0} (2\pi)^{2t} / (n_0 (n_0 - 1) \cdots (n_0 - 2t + 1)) from the transform of Fn0F_{n_0} and cached transforms of (2π)2t(2\pi)^{2t}, at the cost of a division by a short multi-limb integer per number. With threads, the numbers of a batch are tasks taken by the threads (the expensive ones first), and the threads then take chunks of powers for the table pass of the next batch, summing into their own accumulators, which the tasks of the next batch add up. The threads are requested when a batch starts, and the serial scheme is used if none are free.

Threading inside each number (for example in the transforms) does not pay at these sizes, while separate iterators on disjoint ranges of nn, which parallelise perfectly, each need their own table and initialisation and, to yield the numbers in order, the buffering of a whole range. bernoulli_fmpq_vec_no_cache (which fills the cache used by the arb special functions) stores the whole range anyway: with up to three threads it runs one iterator, and with more it runs independent iterators on 32 blocks of the range (largest blocks first), which cost about 1.45 times as much in total but parallelise perfectly.

Harvey's multimodular algorithm#

Harvey [Har2010] computes Bn mod pB_n \bmod p for a prime pp in time O(plog⁡1+o(1)p)O(p \log^{1+o(1)} p), independently of nn:

  1. If (p−1)∣n(p - 1) \mid n, pp divides the denominator. Otherwise, by Kummer's congruence Bn/n≡Bm/m(modp)B_n/n \equiv B_m/m \pmod p for m=n mod (p−1)m = n \bmod (p-1), so it suffices to compute Bm/m mod pB_m/m \bmod p with 2≤m≤p−32 \le m \le p - 3.
  2. Voronoi's congruence expresses (cm−1)Bm/m(c^m - 1) B_m / m, for any cc coprime to pp, as a sum over x∈(Z/pZ)×x \in (\mathbb{Z}/p\mathbb{Z})^\times of xm−1x^{m-1} times a simple function of ⌊cx/p⌋\lfloor cx/p \rfloor. Enumerating xx as the powers of a primitive root gg, and using the symmetry x↔p−xx \leftrightarrow p - x, gives a sum of (p−1)/2(p-1)/2 terms, each one multiplication modulo pp.
  3. With c=2c = 2 (when 2m≢1(modp)2^m \not\equiv 1 \pmod p), the floor terms are the bits of the binary expansion of x/px/p. Harvey reorganises the sum so that the inner loop reads the expansion of 1/p1/p word by word and accumulates into tables indexed by 8-bit chunks; the tables are combined with precomputed weights at the end. This makes the constant very small. If 2m≡12^m \equiv 1, the slower generic sum with c=gc = g is used.

With all primes 5≤p≤X5 \le p \le X, (p−1)∤n(p-1) \nmid n, up to X≈nlog⁡nX \approx n \log n, the product exceeds ∣Nn∣|N_n|, and the Chinese remainder theorem gives the numerator: O(n2log⁡O(1)n)O(n^2 \log^{O(1)} n) operations in total, but fully parallel and with smaller constants than the zeta method for large nn. FLINT combines the two methods: the residues modulo a product MM of primes give the low part r=Nn mod Mr = N_n \bmod M, and the zeta method only needs to find the integer t=(Nn−r)/Mt = (N_n - r)/M, a number with a fraction 1−α1 - \alpha of the bits of NnN_n. The default α\alpha grows from 0 at n=18000n = 18000 to 0.280.28 for large nn.

Asymptotically faster methods exist: Harvey's later algorithm computes BnB_n in O(n4/3+o(1))O(n^{4/3 + o(1)}) bit operations [HarveyBern2014], and Brent and Harvey compute all of B0,…,BnB_0, \ldots, B_n in quasi-optimal time with power series [BrentHarvey2013]; they are not implemented.

Short vectors#

For a vector B0,…,Bn−1B_0, \ldots, B_{n-1} with moderate nn, arith uses:

  • Ramanujan's recursion (_arith_bernoulli_number_vec_recursive, n<700n < 700). Ramanujan's identity [Ram1911]

    (m+3m)Bm={m+33−m+36−∑j=1⌊m/6⌋(m+3m−6j)Bm−6j,m≡0,2 or 4(mod6),\binom{m+3}{m} B_m = \begin{cases} \frac{m+3}{3} \\ -\frac{m+3}{6} \end{cases} - \sum_{j=1}^{\lfloor m/6 \rfloor} \binom{m+3}{m - 6j} B_{m-6j}, \quad m \equiv 0, 2 \text{ or } 4 \pmod 6,

    (with (m+3)/3(m+3)/3 for m≡0,2m \equiv 0, 2 and −(m+3)/6-(m+3)/6 for m≡4m \equiv 4) needs only a sixth of the previous values. FLINT runs it on integers over the common denominator (n+1)#(n + 1)\#, so that no GCD is needed until the final division by the true denominators.

  • Power series modulo primes (_arith_bernoulli_number_vec_multi_mod, n≥700n \ge 700). The even Bernoulli numbers are the coefficients of

    x2cosh⁡x−1=∑k≥0(2−4k) B2k(2k)!x2k,\frac{x^2}{\cosh x - 1} = \sum_{k \ge 0} \frac{(2 - 4k)\, B_{2k}}{(2k)!} x^{2k},

    obtained by one power series inversion of (cosh⁡x−1)/x2(\cosh x - 1)/x^2, which has only the even terms [BuhlerCrandallSompolski1992]. Multiplying by the known denominators and factorials modulo each prime gives the numerators modulo the prime, and Chinese remaindering the numerators.

Euler numbers#

The Euler numbers EnE_n, 1/cosh⁡t=∑Entn/n!1/\cosh t = \sum E_n t^n/n!, are integers with ∣E2m∣=22m+2(2m)! β(2m+1)/π2m+1|E_{2m}| = 2^{2m+2} (2m)!\, \beta(2m+1)/\pi^{2m+1}, where β(s)=∑k≥0(−1)k(2k+1)−s\beta(s) = \sum_{k \ge 0} (-1)^k (2k+1)^{-s} is the Dirichlet beta function. FLINT computes an isolated EnE_n from this formula for n<2000n < 2000 and with a multimodular method combined with the beta function above (arb_fmpz_euler_number_ui), and a vector by inverting the power series of cosh⁡\cosh modulo primes (arith_euler_number_vec).

Use in FLINT#

FunctionMethod
bernoulli_fmpq_uithe cache if possible; zeta for n<18000n < 18000; zeta with multimodular low part above
_bernoulli_fmpq_ui_zetathe zeta function via arb_bernoulli_ui_zeta
_bernoulli_fmpq_ui_multi_modbernoulli_mod_p_harvey on many primes in parallel, plus the zeta function for the high part
bernoulli_mod_p_harveyHarvey's algorithm with Kummer's congruence
bernoulli_rev_init, bernoulli_rev_nextthe reverse iterator Algorithm 1, in batches, threaded
bernoulli_fmpq_vec_no_cache, bernoulli_cache_computeone reverse iterator, or iterators on blocks in parallel (more than three threads)
arith_bernoulli_number_vecRamanujan's recursion (n<700n < 700) or power series modulo primes
arith_euler_number, arith_euler_number_vecthe beta function and multimodular methods; power series modulo primes

The generic functions call these: gr_bernoulli_ui uses bernoulli_fmpq_ui over Q\mathbb{Q} (and in rings without a real precision, followed by a conversion), gr_bernoulli_vec uses bernoulli_fmpq_vec_no_cache over Q\mathbb{Q}, and gr_eulernum_vec uses arith_euler_number_vec over Z\mathbb{Z}; in real and complex rings they compute numerically with arb.

Referenced from#

References#

  • [IR1990] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, second edition, Graduate Texts in Mathematics 84, Springer, 1990. https://doi.org/10.1007/978-1-4757-2103-4
  • [Coh2007b] H. Cohen, Number Theory, Volume II: Analytic and Modern Tools, Graduate Texts in Mathematics 240, Springer, 2007. https://doi.org/10.1007/978-0-387-49894-2
  • [Blo2009] R. Bloemen, "Even faster zeta(2n) calculation!", https://web.archive.org/web/20141101133659/http://xn--2-umb.com/09/11/even-faster-zeta-calculation
  • [Har2010] D. Harvey, "A multimodular algorithm for computing Bernoulli numbers" (2010), Mathematics of Computation 79.272: 2361-2370
  • [HarveyBern2014] D. Harvey, "A subquadratic algorithm for computing the n-th Bernoulli number", Mathematics of Computation 83 (2014), 2471–2477. https://doi.org/10.1090/S0025-5718-2014-02832-X
  • [BrentHarvey2013] R. P. Brent and D. Harvey, "Fast computation of Bernoulli, tangent and secant numbers", in Computational and Analytical Mathematics, Springer Proceedings in Mathematics & Statistics 50 (2013), 127–142. https://doi.org/10.1007/978-1-4614-7621-4_8
  • [Ram1911] S. Ramanujan, "Some properties of Bernoulli's numbers", Journal of the Indian Mathematical Society 3 (1911), 219–234.
  • [BuhlerCrandallSompolski1992] Buhler, J.P. and Crandall, R.E. and Sompolski, R.W. : Irregular primes to one million : Math. Comp. 59:2000 (1992) 717–722
Cite this page

The FLINT team, “Bernoulli numbers,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/number-theory/bernoulli.html (generated 2026-11-20).