Bernoulli numbers
- Cost
- bit operations for an isolated by either the zeta or the multimodular method; with a small constant for all of with the reverse iterator.
The Bernoulli numbers are the rational numbers defined by . They vanish for odd , alternate in sign for even , and grow quickly:
The numerator of thus has about bits; that of 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 ,
the sum running over the primes with . In particular the denominator of in lowest terms is , squarefree and divisible by 6.
The denominator is therefore found from the divisors of (arith_bernoulli_number_denom tests the primes up to , with a table for ). It is small: at most , so it has at most bits, and usually far fewer. All methods below therefore compute the numerator , an integer.
The zeta function method#
Since is known, it suffices to compute numerically with an absolute error below , that is, to about significant bits. With bits of precision, the formula above needs and (cheap: binary splitting and a power) and , which is and for which very few terms are needed:
so terms suffice, which is for . Equivalently one evaluates the Euler product over primes, with factors. FLINT's arb_bernoulli_ui_zeta uses the Euler product when is small compared with the precision and an asymptotic expansion of otherwise, in ball arithmetic. _bernoulli_fmpq_ui_zeta multiplies the ball by and returns the unique integer it contains (increasing the precision in the unlikely event that the ball contains two). Each power costs , so the total is , about bit operations.
The reverse iterator#
To compute all of , evaluating each from scratch would cost . Bloemen's observation [Blo2009] is that the power table can be shared: if the powers are stored in fixed point with fractional bits, then is one multiplication by a word. Going down in 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.
Input: an even .
Output: .
- Choose the precision from the size of and of its denominator, and .
- For odd compute with a bound on the rounding error. Compute .
For :
- encloses up to the accumulated rounding errors and the tail of the series.
- ; ; round to the integer, if the error bound allows it.
- Update , .
- Now and then, lower and to the values needed for the current , truncating the .
Each step costs multiplications of a -bit number by a word, bit operations, plus two multiplications of -bit numbers, so all the even Bernoulli numbers up to cost 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 consecutive indices ( below ) and yielded from a buffer. Step 3.1 for the whole batch is one pass over the table: for each , the multiplications by and the additions into the sums are done while the number is in cache. The frame and the number of terms are lowered at every batch.
- The table. With AVX-512 IFMA, the are stored as digits of 50 bits (redundant, below ) in 64-bit lanes, multiplied by with
vpmadd52luq/vpmadd52huqand summed without carries, the digit sums being converted to limbs every 4096 powers; this needs . Otherwise the table is in limbs, updated bympn_mul_1and summed bympn_add_ndirectly 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 times while in cache and the blocks of the sums serve all eight powers; streaming each power and the sums times over is bound by the memory bandwidth once the powers exceed the L2 cache (half the speed for powers of limbs on one thread). In step 2 the powers of the primes are computed by powering in ball arithmetic and those of the composites ( the smallest prime factor) as from the top limbs of the entries of and , so that nothing beyond the table is held; the primes, and then the composites in for (whose cofactors are below ), are done in parallel. The table takes about bits; it shrinks as decreases (the frame is lowered by about bits per step while grows by bits, ), and a buffer is reallocated when it is more than about 1/8 empty. - The sieve. For , the table only holds the prime to and and, apart, the -smooth (3, 5, 9, 15, 25, ..., a few dozen): by unique factorization with and the sums over the smooth and the prime-to-15 , up to terms with distinct odd , which the tail bound covers. This costs one product per number, of the size of in the frame, and removes of the and about as much of the table (more of the small , 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. is a floating-point number of limbs. The two products of a step, and , both only need the high half: is aligned so that both read the window of limbs of a product of -limb operands, and with
fft_smallthe forward transform of is shared by the two products and that of is cached, so that a step costs four transforms. is lowered in steps of about 3%, so that the transform plan serves many batches. The division by in step 3.2 is done in linear time, by summing the -bit chunks of the dividend from the top. - Rounding. All the error terms are tracked, and the fraction of must stay away from by more than the error bound; otherwise (which is not expected to happen) is computed by
_bernoulli_fmpq_ui. - Threads. The numbers of a batch become independent if the prefactors are obtained as from the transform of and cached transforms of , 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 , 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 for a prime in time , independently of :
- If , divides the denominator. Otherwise, by Kummer's congruence for , so it suffices to compute with .
- Voronoi's congruence expresses , for any coprime to , as a sum over of times a simple function of . Enumerating as the powers of a primitive root , and using the symmetry , gives a sum of terms, each one multiplication modulo .
- With (when ), the floor terms are the bits of the binary expansion of . Harvey reorganises the sum so that the inner loop reads the expansion of 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 , the slower generic sum with is used.
With all primes , , up to , the product exceeds , and the Chinese remainder theorem gives the numerator: operations in total, but fully parallel and with smaller constants than the zeta method for large . FLINT combines the two methods: the residues modulo a product of primes give the low part , and the zeta method only needs to find the integer , a number with a fraction of the bits of . The default grows from 0 at to for large .
Asymptotically faster methods exist: Harvey's later algorithm computes in bit operations [HarveyBern2014], and Brent and Harvey compute all of in quasi-optimal time with power series [BrentHarvey2013]; they are not implemented.
Short vectors#
For a vector with moderate , arith uses:
Ramanujan's recursion (
_arith_bernoulli_number_vec_recursive, ). Ramanujan's identity [Ram1911](with for and for ) needs only a sixth of the previous values. FLINT runs it on integers over the common denominator , so that no GCD is needed until the final division by the true denominators.
Power series modulo primes (
_arith_bernoulli_number_vec_multi_mod, ). The even Bernoulli numbers are the coefficients ofobtained by one power series inversion of , 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 , , are integers with , where is the Dirichlet beta function. FLINT computes an isolated from this formula for 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 modulo primes (arith_euler_number_vec).
Use in FLINT#
| Function | Method |
|---|---|
bernoulli_fmpq_ui | the cache if possible; zeta for ; zeta with multimodular low part above |
_bernoulli_fmpq_ui_zeta | the zeta function via arb_bernoulli_ui_zeta |
_bernoulli_fmpq_ui_multi_mod | bernoulli_mod_p_harvey on many primes in parallel, plus the zeta function for the high part |
bernoulli_mod_p_harvey | Harvey's algorithm with Kummer's congruence |
bernoulli_rev_init, bernoulli_rev_next | the reverse iterator Algorithm 1, in batches, threaded |
bernoulli_fmpq_vec_no_cache, bernoulli_cache_compute | one reverse iterator, or iterators on blocks in parallel (more than three threads) |
arith_bernoulli_number_vec | Ramanujan's recursion () or power series modulo primes |
arith_euler_number, arith_euler_number_vec | the beta function and multimodular methods; power series modulo primes |
The generic functions call these: gr_bernoulli_ui uses bernoulli_fmpq_ui over (and in rings without a real precision, followed by a conversion), gr_bernoulli_vec uses bernoulli_fmpq_vec_no_cache over , and gr_eulernum_vec uses arith_euler_number_vec over ; in real and complex rings they compute numerically with arb.
void bernoulli_fmpq_ui(fmpq_t b, ulong n)void bernoulli_fmpq_vec_no_cache(fmpq * res, ulong a, slong num)void arith_bernoulli_number_vec(fmpq * x, slong n)Referenced from#
- Mathematical constants (algorithm)
- The gamma function (algorithm)
arb_bernoulli_ui,arb_bernoulli_fmpzarb_fmpz_euler_number_ui,arb_fmpz_euler_number_ui_multi_mod- arith.h (module)
- bernoulli.h (module)
bernoulli_rev_tbernoulli_rev_init- Isolated Bernoulli numbers
gr_bernoulli_ui,gr_bernoulli_fmpz,gr_bernoulli_vec
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
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).
@misc{flint-doc-algorithms-number-theory-bernoulli,
author = {{The FLINT team}},
title = {{Bernoulli numbers}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/number-theory/bernoulli.html},
note = {Generated 2026-11-20}
}