FLINT3.7.0-dev
Algorithm

Mathematical constants

Cost
O(M(n)log⁡2n)O(M(n) \log^2 n) for the hypergeometric constants by binary splitting (Γ(1/4)\Gamma(1/4) from 2162^{16} limbs in O(M(n)log⁡n)O(M(n)\log n) plus the cost of π\pi) and O(M(n)nlog⁡n)O(M(n) \sqrt{n} \log n) for the reciprocal Fibonacci constant; Khinchin's constant in O(n3/log⁡3n)O(n^3/\log^3 n) word operations by sums of zeta values and in O(n M(n)log⁡2n)O(\sqrt n\, M(n) \log^2 n) by the approximate functional equation; Glaisher's constant (below about 10510^5 to 3.5⋅1053.5 \cdot 10^5 bits, depending on the number of threads) uses sums of many full-precision terms and is much slower, and costs O~(n1.5)\tilde O(n^{1.5}) at higher precision.

Most of the mathematical constants of FLINT are sums of hypergeometric series, series whose term ratio is a rational function of the index, and are evaluated by binary splitting. The series for π\pi, ee, log⁡2\log 2, log⁡10\log 10, γ\gamma, Catalan's constant, ζ(3)\zeta(3), ζ(5)\zeta(5), Γ(1/3)\Gamma(1/3) and Γ(1/4)\Gamma(1/4), and Khinchin's constant, are summed by the mp_real module, which arb_const_pi and the other arb_const_ functions call through _mp_real_const_arb; the same values, kept as exact floors, serve the argument reductions of the elementary functions (Elementary functions). The formulas were taken from the collection of y-cruncher [Yee2025], and for each constant the formula measured fastest in this implementation was chosen.

Binary splitting#

Consider a sum S=∑k=0N−1a(k)/b(k)⋅∏j<kp(j)/q(j)S = \sum_{k=0}^{N-1} a(k)/b(k) \cdot \prod_{j<k} p(j)/q(j) with polynomials a,b,p,qa, b, p, q with integer coefficients. For 0≤u<v≤N0 \le u < v \le N define P(u,v)=∏j=uv−1p(j)P(u, v) = \prod_{j=u}^{v-1} p(j), Q(u,v)=∏j=uv−1q(j)Q(u, v) = \prod_{j=u}^{v-1} q(j), and T(u,v)=Q(u,v)∑k=uv−1(…)T(u, v) = Q(u, v) \sum_{k=u}^{v-1} (\ldots), the partial sum scaled to an integer. Then for u<w<vu < w < v

P(u,v)=P(u,w)P(w,v),Q(u,v)=Q(u,w)Q(w,v),T(u,v)=T(u,w)Q(w,v)+P(u,w)T(w,v)P(u, v) = P(u, w) P(w, v), \quad Q(u, v) = Q(u, w) Q(w, v), \quad T(u, v) = T(u, w) Q(w, v) + P(u, w) T(w, v)

(with the obvious extension for a/ba/b), so the exact sum is obtained by a balanced recursion and one final division T/QT/Q.

Proposition 1. If the series converges geometrically, so that N=O(n)N = O(n) terms give nn bits, and the integers P(u,v),Q(u,v),T(u,v)P(u, v), Q(u, v), T(u, v) have O((v−u)log⁡v)O((v - u) \log v) bits, binary splitting computes SS to nn bits in O(M(nlog⁡n)log⁡n)O(M(n \log n) \log n) bit operations, which is O(M(n)log⁡2n)O(M(n) \log^2 n).

Proof. At each of the O(log⁡N)O(\log N) levels of the recursion, the numbers multiplied have a total size of O(Nlog⁡N)=O(nlog⁡n)O(N \log N) = O(n \log n) bits, and multiplication is superadditive, so each level costs O(M(nlog⁡n))O(M(n \log n)). The final division costs O(M(n))O(M(n)).

The series below add between 2 and 47 bits per term. The constant factor is what distinguishes the formulas, and it is governed by the number of bits per term and the size of the coefficients [HP1998] [BZ2011].

In mp_real the splitting is mp_real_hypgeom_series (Binary splitting of hypergeometric series in mp_real), which sums a series given by integer polynomials PP, QQ, RR in the format of y-cruncher's formula files, with rigorous tail bounds and threads. Since it gives FLINT_BITS(n−1)\mathtt{FLINT\_BITS}(n - 1) correct bits, the constants call it with one limb more than they need.

The series#

ConstantFormula
π\piChudnovsky [CC1988], π=S/10005\pi = S/\sqrt{10005} (see below), 47.1 bits per term
log⁡2\log 2Zuniga [Zun2025], 12160∑k≥0(1497+1794k)∏j=1kj(2j−1)216(6j+1)(6j+5)\frac{1}{2160}\sum_{k \ge 0}(1497 + 1794k)\prod_{j=1}^k \frac{j(2j-1)}{216(6j+1)(6j+5)}, 11.9 bits per term
ee∑k≥01/k!\sum_{k \ge 0} 1/k!
GGPilehrood [PP2010], 164∑k≥1256k(580k2−184k+15)(2k)!3(3k)!2k3(2k−1)(6k)!2\frac{1}{64}\sum_{k \ge 1}\frac{256^k(580k^2 - 184k + 15)(2k)!^3(3k)!^2}{k^3(2k-1)(6k)!^2}
ζ(3)\zeta(3)a series of Zuniga (2023) with a numerator of degree 11
ζ(5)\zeta(5)Sun's identity (2025), ζ(5)=(3S+56π2ζ(3))/540\zeta(5) = (3S + 56\pi^2\zeta(3))/540 with a 3F2{}_3F_2-type series SS
Γ(1/3)\Gamma(1/3)(8101/4π/X)1/3(810^{1/4}\pi/X)^{1/3} with Guillera's series XX (2023)
Γ(1/4)\Gamma(1/4)(π6/(322S4))1/8(\pi^6/(322S^4))^{1/8} with Ebisu's series SS (2016), or the AGM

π\pi#

π\pi is computed by the Chudnovsky series [CC1988]

1π=12∑k=0∞(−1)k(6k)! (13591409+545140134k)(3k)! (k!)3 6403203k+3/2,\frac{1}{\pi} = 12 \sum_{k=0}^{\infty} \frac{(-1)^k (6k)!\,(13591409 + 545140134 k)}{(3k)!\,(k!)^3\, 640320^{3k + 3/2}},

which adds about 47 bits (14 digits) per term. Methods based on the arithmetic-geometric mean [Sal1976] [Bre1976agm] have a better asymptotic complexity, O(M(n)log⁡n)O(M(n) \log n), but are about three times slower in practice. arb_const_sqrt_pi and arb_const_log_sqrt2pi are computed from arb_const_pi with arb_sqrt and arb_log.

The Chudnovsky series in the format of mp_real_hypgeom_series is S=((cQ+cP∑k≥1P(k)Q(k)∏j<kR(j)Q(j))/cD)−1S = \bigl((c_Q + c_P\sum_{k \ge 1}\frac{P(k)}{Q(k)}\prod_{j<k}\frac{R(j)}{Q(j)})/c_D\bigr)^{-1} with cP=1c_P = 1, cQ=13591409c_Q = 13591409, cD=4270934400c_D = 4270934400, R(k)=(6k−5)(2k−1)(6k−1)R(k) = (6k - 5)(2k - 1)(6k - 1), P(k)=(13591409+545140134k)R(k)P(k) = (13591409 + 545140134k)R(k) and Q(k)=−(6403203/24)k3Q(k) = -(640320^3/24)k^3, and π=S/10005\pi = S/\sqrt{10005}; the example on Hypergeometric series runs it.

ee#

e=∑k≥01/k!e = \sum_{k \ge 0} 1/k! is summed by binary splitting, with P=1P = 1 and Q(k)=kQ(k) = k; this is the simplest hypergeometric series and its cost is dominated by the final division.

Logarithms of integers#

log⁡2\log 2 is computed by Zuniga's series [Zun2025]

log⁡2=12160∑k=0∞(1497+1794k)∏j=1kj(2j−1)216(6j+1)(6j+5),\log 2 = \frac{1}{2160} \sum_{k=0}^{\infty} (1497 + 1794 k) \prod_{j=1}^{k} \frac{j (2j - 1)}{216 (6j + 1)(6j + 5)},

which adds 11.9 bits per term. (Earlier versions used another series of Zuniga [Zun2023b], with terms decreasing like 3888−k3888^{-k}.) log⁡10=log⁡2+log⁡5\log 10 = \log 2 + \log 5 uses the Machin-type formulas for the first three primes in terms of

atanh⁡(1/31),atanh⁡(1/49),atanh⁡(1/161),\operatorname{atanh}(1/31), \quad \operatorname{atanh}(1/49), \quad \operatorname{atanh}(1/161),

for example log⁡10=46atanh⁡(1/31)+34atanh⁡(1/49)+20atanh⁡(1/161)\log 10 = 46 \operatorname{atanh}(1/31) + 34 \operatorname{atanh}(1/49) + 20 \operatorname{atanh}(1/161), with the three series evaluated in parallel (each by Zuniga's series where faster; Computing the logarithms). The logarithms of more primes, used by the elementary functions (Elementary functions), come from larger sets of such formulas (arb_log_primes_vec_bsplit).

Euler's constant#

Euler's constant γ\gamma is computed by the Brent-McMillan formula [BM1980] [MPFR2012]

γ=S0(2n)−K0(2n)I0(2n)−log⁡n,\gamma = \frac{S_0(2n) - K_0(2n)}{I_0(2n)} - \log n,

where nn is a free parameter and

S0(x)=∑k=0∞Hk(k!)2(x2)2k,I0(x)=∑k=0∞1(k!)2(x2)2k,2xI0(x)K0(x)∼∑k=0∞[(2k)!]3(k!)482kx2k.S_0(x) = \sum_{k=0}^{\infty} \frac{H_k}{(k!)^2} \left(\frac{x}{2}\right)^{2k}, \quad I_0(x) = \sum_{k=0}^{\infty} \frac{1}{(k!)^2} \left(\frac{x}{2}\right)^{2k}, \quad 2x I_0(x) K_0(x) \sim \sum_{k=0}^{\infty} \frac{[(2k)!]^3}{(k!)^4 8^{2k} x^{2k}}.

The first two series are summed together up to k=N−1k = N - 1 with N≥αn+1N \ge \alpha n + 1, where α≈4.9706257595442318644\alpha \approx 4.9706257595442318644 satisfies α(log⁡α−1)=3\alpha(\log \alpha - 1) = 3, and the asymptotic series up to k=2n−1k = 2n - 1. With these parameters the error is bounded by 24e−8n24 e^{-8n} [BJ2013].

Below 3456 bits γ\gamma comes from a static table. Otherwise, writing mm for the parameter nn, S0S_0 and I0I_0 come from one binary splitting over about 4.97m4.97m terms in dual numbers.

Proposition 2. Let F(ε)=∑k≥0m2k/∏j=1k(j+ε)2F(\varepsilon) = \sum_{k \ge 0} m^{2k}\big/\prod_{j=1}^k (j + \varepsilon)^2 over Q[ε]/(ε2)\mathbb{Q}[\varepsilon]/(\varepsilon^2). Then I0=F(0)I_0 = F(0) and S0=−12F′(0)S_0 = -\tfrac12 F'(0).

Proof. ddε∏j=1k(j+ε)−2∣ε=0=−2∑j=1k1j∏j=1kj−2=−2Hk/k!2\frac{d}{d\varepsilon}\prod_{j=1}^k (j + \varepsilon)^{-2}\big|_{\varepsilon=0} = -2\sum_{j=1}^k \frac1j \prod_{j=1}^k j^{-2} = -2H_k/k!^2.

The splitting of FF carries a scalar PP, a dual number D=D0+D1ε=∏(k+1+ε)D = D_0 + D_1\varepsilon = \prod(k + 1 + \varepsilon) (so that the denominator is D2D^2) and T=T0+T1εT = T_0 + T_1\varepsilon, merged as

T=P1T2+D22T1,D=D1D2,P=P1P2,T = P_1 T_2 + D_2^2 T_1, \qquad D = D_1D_2, \qquad P = P_1P_2,

five full-size and five half-size products per merge. At the end, with X=T0+D02X = T_0 + D_0^2,

S0I0=2T0D1−T1D02D0X,K0I02=D04 TKX2QK,\frac{S_0}{I_0} = \frac{2T_0D_1 - T_1D_0}{2D_0X}, \qquad \frac{K_0}{I_0^2} = \frac{D_0^4\, T_K}{X^2 Q_K},

where TK/QKT_K/Q_K is a second splitting over 2m2m terms at half the precision. The main sum runs first and leaves only its quotient and two half-precision values, so that the peak memory is that of the main sum.

The parameter mm is rounded up so that log⁡m\log m is a combination of a few fast logarithms: over the primes {2}\{2\}, {2,3}\{2, 3\}, {2,3,5}\{2, 3, 5\} or {2,3,5,7}\{2, 3, 5, 7\}, using log⁡(9/8)\log(9/8) and log⁡(256/243)\log(256/243); log⁡(81/80)\log(81/80), log⁡(32805/32768)\log(32805/32768) and log⁡(25/24)\log(25/24); or log⁡(2401/2400)\log(2401/2400), log⁡(4375/4374)\log(4375/4374), log⁡(225/224)\log(225/224) and log⁡(64/63)\log(64/63), each by Zuniga's series. The splittings cost about m(61+log⁡2o)m(61 + \log_2 o) for the odd part oo of mm (powers of two in mm are free), so every m∈[m0,1.5m0]m \in [m_0, 1.5m_0] smooth over {2,3,5,7}\{2, 3, 5, 7\} is scored by this cost plus that of its logarithms, and the best is taken (_mp_real_const_euler_tune forces the set of primes).

Catalan's constant#

Catalan's constant is computed by the series of Pilehrood and Pilehrood [PP2010]

G=164∑k=1∞256k(580k2−184k+15) (2k)!3 (3k)!2k3(2k−1) (6k)!2,G = \frac{1}{64} \sum_{k=1}^{\infty} \frac{256^k (580 k^2 - 184 k + 15) \,(2k)!^3\,(3k)!^2}{k^3 (2k - 1)\,(6k)!^2},

which adds about 5.4 bits per term and was measured to be the fastest available formula.

ζ(3)\zeta(3) and ζ(5)\zeta(5)#

Apéry's constant ζ(3)\zeta(3) is computed by a hypergeometric series found by Zuniga [Zun2023],

ζ(3)=148∑k=1∞(−1)k−1P(k)k5(2k−1)3(3k−1)(3k−2)(4k−1)(4k−3)(6k−1)(6k−5)(5kk)(5k2k)(9k4k)(10k5k)(12k6k),\zeta(3) = \frac{1}{48} \sum_{k=1}^{\infty} \frac{(-1)^{k-1} P(k)}{k^5 (2k-1)^3 (3k-1)(3k-2)(4k-1)(4k-3)(6k-1)(6k-5) \binom{5k}{k}\binom{5k}{2k}\binom{9k}{4k}\binom{10k}{5k}\binom{12k}{6k}},

with P(k)P(k) a polynomial of degree 11 given in the source. ζ(5)\zeta(5) is computed from Z.-W. Sun's identity

ζ(5)=3S+56π2ζ(3)540,S=∑n=1∞(−127)n(560n4−640n3+408n2−136n+17) n!2(1/3)n(2/3)n n5(2n−1)4,\zeta(5) = \frac{3 S + 56 \pi^2 \zeta(3)}{540}, \quad S = \sum_{n=1}^{\infty} \left(-\frac{1}{27}\right)^n \frac{(560 n^4 - 640 n^3 + 408 n^2 - 136 n + 17)\, n!^2}{(1/3)_n (2/3)_n\, n^5 (2n-1)^4},

with the three parts SS, ζ(3)\zeta(3) and π\pi computed in parallel when threads are available.

Γ(1/3)\Gamma(1/3) and Γ(1/4)\Gamma(1/4)#

Γ(1/3)=(8101/4π/X)1/3\Gamma(1/3) = (810^{1/4}\pi/X)^{1/3} with Guillera's series XX (2023), and Γ(1/4)=(π6/(322S4))1/8\Gamma(1/4) = (\pi^6/(322S^4))^{1/8} with Ebisu's series SS (2016); the series and π\pi run on separate threads. For Γ(1/4)\Gamma(1/4) above 2162^{16} limbs, the formula

Γ(1/4)=(2π)3/2agm⁡(1,2)\Gamma(1/4) = \sqrt{\frac{(2\pi)^{3/2}}{\operatorname{agm}(1, \sqrt 2)}}

is used instead, with the AGM (O(M(n)log⁡n)O(M(n)\log n)) computed in parallel with π\pi.

Khinchin's constant#

Zeta expansion#

Up to about 1.5⋅1061.5 \cdot 10^6 digits, Khinchin's constant KK is computed from the formula [BBC1997]

log⁡K=1log⁡2[−∑k=2K0−1log⁡(k−1k)log⁡(k+1k)+∑n=1∞ζ(2n,K0)n∑k=12n−1(−1)k+1k],\log K = \frac{1}{\log 2} \left[ -\sum_{k=2}^{K_0-1} \log \left(\frac{k-1}{k}\right) \log \left(\frac{k+1}{k}\right) + \sum_{n=1}^{\infty} \frac{\zeta(2n, K_0)}{n} \sum_{k=1}^{2n-1} \frac{(-1)^{k+1}}{k} \right],

where K0≥2K_0 \ge 2 is a free parameter. The finite sum has a minus sign: each product of logarithms is negative. arb_const_khinchin calls mp_real_const_khinchin, which takes K0K_0 between 6 and 12, evaluates the finite sum as a quadratic form in the logarithms of the primes up to K0K_0, and computes the ζ(2n,K0)\zeta(2n, K_0) by direct summation with recycled powers for large nn and from exact Bernoulli numbers for small nn (below).

Proposition 3 (Truncation error). If the series over nn is truncated after n=Mn = M, the error inside the brackets is at most 1/K02M1/K_0^{2M}.

Proof. The inner alternating sums lie in (0,1](0, 1], so the remainder is bounded in absolute value by ∑n>Mζ(2n,K0)/n≤∑n>Mζ(2n,K0)\sum_{n > M} \zeta(2n, K_0)/n \le \sum_{n > M} \zeta(2n, K_0). By the integral bound,

∑n=M+1∞ζ(2n,K0)=∑n=M+1∞∑k=0∞(k+K0)−2n≤∑n=M+1∞(K0−2n+∫0∞(t+K0)−2n dt)=∑n=M+1∞1K02n(1+K02n−1),\sum_{n=M+1}^{\infty} \zeta(2n, K_0) = \sum_{n=M+1}^{\infty} \sum_{k=0}^{\infty} (k + K_0)^{-2n} \le \sum_{n=M+1}^{\infty} \left(K_0^{-2n} + \int_0^{\infty} (t + K_0)^{-2n}\, dt\right) = \sum_{n=M+1}^{\infty} \frac{1}{K_0^{2n}} \left(1 + \frac{K_0}{2n - 1}\right),

and since K0/(2n−1)≤K0K_0/(2n - 1) \le K_0, this is at most ∑n>M(K0+1)K0−2n=1K02M(K0−1)≤1K02M\sum_{n > M} (K_0 + 1) K_0^{-2n} = \frac{1}{K_0^{2M}(K_0 - 1)} \le \frac{1}{K_0^{2M}}.

For an error of 2−p2^{-p} it therefore suffices to take M≥p/(2log⁡2K0)M \ge p / (2 \log_2 K_0).

The algorithm#

With f(x)=−log⁡(1−x)log⁡(1+x)=∑n≥1cnx2nf(x) = -\log(1-x)\log(1+x) = \sum_{n \ge 1} c_n x^{2n}, cn=An/nc_n = A_n/n and An=1−12+13−⋯+12n−1A_n = 1 - \tfrac12 + \tfrac13 - \cdots + \tfrac{1}{2n-1},

S=log⁡Klog⁡2=∑k≥2f(1/k)=∑k=2K0−1f(1/k)+∑n≥1cn ζ(2n,K0),S = \log K \log 2 = \sum_{k \ge 2} f(1/k) = \sum_{k=2}^{K_0-1} f(1/k) + \sum_{n \ge 1} c_n\,\zeta(2n, K_0),

the classical sum over ζ(2n)−1\zeta(2n) - 1 [BBC1997] being the case K0=2K_0 = 2. Each cell (k,n)(k, n) of the double sum ∑k∑ncnk−2n\sum_k\sum_n c_n k^{-2n} is covered in one of three ways.

Rows k<K0k < K_0 use f(1/k)=(ℓk−ℓk−1)(ℓk+1−ℓk)f(1/k) = (\ell_k - \ell_{k-1})(\ell_{k+1} - \ell_k) with ℓm=log⁡m\ell_m = \log m, an integer combination of the logarithms λj\lambda_j of the primes up to K0K_0, which come from one set of Machin-type series (Computing the logarithms). The sum of the rows is a quadratic form ∑Cijλiλj\sum C_{ij}\lambda_i\lambda_j with small integer CC, so it costs one full product per prime rather than one per row.

Columns n≥n1n \ge n_1 sum ζ(2n,K0)=∑k≥K0k−2n\zeta(2n, K_0) = \sum_{k \ge K_0} k^{-2n} directly, in fixed point with WW fraction limbs, over the kk with k−2n≥B−Wk^{-2n} \ge B^{-W}. The powers are recycled from column to column, downward: k−2nBW+ek^{-2n}B^{W+e} is kept as an integer with ee extended limbs and stepped by one mpn_mul_1 by k2k^2, several times faster than the division by k2k^2 an upward recurrence needs. A downward step multiplies the absolute error by k2k^2 but keeps the relative error, so a power is created (binary powering and one division) with the relative accuracy needed at the bottom of its range, its bottom limb is dropped whenever its error count passes 220B2^{20}B (so that the truncations, one unit of the next limb each, cost a negligible relative amount over thousands of drops), and the range is cut into up to three segments, each created afresh, so that the products shorten with the accuracy actually needed. Only k∈[K0,2K0)k \in [K_0, 2K_0) and the odd k≥2K0k \ge 2K_0 are summed: the even k≥2K0k \ge 2K_0 contribute 4−nζ(2n,K0)4^{-n}\zeta(2n, K_0), so the partial sum is divided by 1−4−n1 - 4^{-n} by a few shifted additions.

Streaming every power, and the column sum, once per column is bound by the memory bandwidth once the powers outgrow the L2 cache, and the more so the more threads share it. The columns are therefore taken in batches of 16 with one partial sum per column, and the powers eight at a time by blocks of 256 limbs of the column sums: each block of a power is stepped through the 16 columns while in cache, and the blocks of the 16 sums serve the eight powers. The drops of bottom limbs depend only on the error counts, so they are scheduled before the products, which are those of the column-by-column recurrence; the carries between blocks are kept per power and column. This roughly halves the time per limb and step on one thread for powers of 2⋅1052 \cdot 10^5 limbs, at a cost of 16 column sums of WW limbs per task. The subtracted powers k<K0k < K_0 of the Bernoulli columns (below) are summed the same way.

Columns n<n1n < n_1 use ζ(2n,K0)=ζ(2n)−1−∑k<K0k−2n\zeta(2n, K_0) = \zeta(2n) - 1 - \sum_{k<K_0} k^{-2n} with ζ(2n)=∣B2n∣(2π)2n/(2(2n)!)\zeta(2n) = |B_{2n}|(2\pi)^{2n}/(2(2n)!) and the exact Bernoulli numbers of the reverse iterator bernoulli_rev [Blo2009], which recycles odd powers downward at the precision of B2nB_{2n}, below the working precision for these nn. The factor tn=(2π)2n/(2n)!t_n = (2\pi)^{2n}/(2n)! would cost one full product per column; instead the columns are taken in blocks [lo,hi][lo, hi] of b≈min⁡(2n1,128)b \approx \min(2\sqrt{n_1}, 128) and computed in units of thit_{hi},

ζ(2m)thi=∣B2m∣ (2m+1)⋯(2 hi)2 (2π)−2(hi−m),\frac{\zeta(2m)}{t_{hi}} = \frac{|B_{2m}|\,(2m+1)\cdots(2\,hi)}{2}\,(2\pi)^{-2(hi-m)},

with the powers (2π)−2j(2\pi)^{-2j}, j≤bj \le b, computed once: a column then costs one product of the integer by a full-precision power, and a block four full products.

The weights cnc_n are applied by summation by parts: with a1=1a_1 = 1, ai=−1/((2i−2)(2i−1))a_i = -1/((2i-2)(2i-1)), so that An=a1+⋯+anA_n = a_1 + \cdots + a_n, and Ri=∑lo≤n≤hi, n≥iXn/nR_i = \sum_{lo \le n \le hi,\, n \ge i} X_n/n,

∑n=lohicnXn=Alo−1Rlo+∑i=lohiaiRi,\sum_{n=lo}^{hi} c_n X_n = A_{lo-1}R_{lo} + \sum_{i=lo}^{hi} a_i R_i,

two single-limb divisions and two additions per column instead of a product by the real AnA_n. Since ζ(2n,K0)≈K0−2n\zeta(2n, K_0) \approx K_0^{-2n}, the suffix sums of the direct columns only occupy the low limbs, and their cost tapers off with the column. All fixed-point errors are counted in ulps and bounded rigorously, including the omitted terms ∑k≥k1k−2n≤k1−2n(1+k1/(2n−1))\sum_{k \ge k_1} k^{-2n} \le k_1^{-2n}(1 + k_1/(2n-1)) and the columns beyond the last one.

A direct column nn costs about (K(n)−K0)/2(K(n) - K_0)/2 products of single limbs by numbers of up to WW limbs, with K(n)=BW/2nK(n) = B^{W/2n}, and a Bernoulli column about two products of the size sns_n of B2nB_{2n} (in the iterator) and one of size sns_n by WW limbs; n1n_1 is chosen where K(n1)K(n_1) is between 232^3 and 2132^{13} (measured), growing with the precision up to 3⋅1063 \cdot 10^6 bits. Beyond, n1n_1 is chosen so that B2n1B_{2n_1} has about as many bits as the working precision, so that the direct column n1n_1 takes about as many powers as the iterator does there (K(n1)≈216.8K(n_1) \approx 2^{16.8} at 10710^7 digits); otherwise the Bernoulli columns, whose cost grows like the cube of the precision with n1n_1 fixed, would take nearly all the time. For nn limbs, the full products cost O(n M(n)/log⁡n)O(n\,M(n)/\log n) in all, and the power sums of the iterator and the direct columns O(n3/log⁡3n)O(n^3/\log^3 n) word operations, which dominate at very high precision.

The sums being linear, the direct columns are split into groups of kk (two per thread), the subtracted powers ∑k<K0k−2n\sum_{k<K_0} k^{-2n} into ranges of columns (with Alo−1=H2lo−3−Hlo−2A_{lo-1} = H_{2lo-3} - H_{lo-2} from exact harmonic numbers) and the Bernoulli columns into ranges of nn, each with its own summation by parts, which run as independent tasks together with the rows. Each range of Bernoulli columns has its own iterator, whose power table takes about (2 hi)2/24(2\,hi)^2/24 bits (The reverse iterator), which dominates the memory at high precision: with one range per thread, some five times the table of the top range at once (about 5 GB at 2⋅1062 \cdot 10^6 digits). The ranges are therefore run one per thread only while their tables total below 1 GiB; beyond, as many ranges run at once as stay below it (at least one), each with the threads left over, used inside the iterator and for the columns: a group of 16 columns takes its 16 numbers from the iterator, then their products by the powers of (2π)−2(2\pi)^{-2} in parallel, the prefix sums RiR_i, and the divisions by (2i−2)(2i−1)(2i-2)(2i-1) in parallel, the ∑ai\sum a_i of a block being summed exactly. The direct columns, the subtracted powers and the rows then follow. _mp_real_const_khinchin_tune forces K0K_0, n1n_1 and the number of Bernoulli ranges run at once.

The approximate functional equation#

From MP_REAL_KHINCHIN_AFE_CUTOFF limbs (about 1.5⋅1061.5 \cdot 10^6 digits), mp_real_const_khinchin uses _mp_real_const_khinchin_afe, which needs O(n)O(\sqrt n) evaluations of cost O(M(n)log⁡2n)O(M(n)\log^2 n) each instead of the cubic power sums above. It starts from the dilogarithm series of [BBC1997, §3],

log⁡Klog⁡2=log⁡22+Li⁡2(−12)+12∑k≥2(−1)kLi⁡2(4/k2),\log K \log 2 = \log^2 2 + \operatorname{Li}_2(-\tfrac12) + \tfrac12 \sum_{k \ge 2} (-1)^k \operatorname{Li}_2(4/k^2),

and the Laplace transform Li⁡2(4/K)=∫0∞e−KuG(u) du\operatorname{Li}_2(4/K) = \int_0^\infty e^{-Ku} G(u)\,du for K>4K > 4, with G(u)=E(4u)/uG(u) = E(4u)/u and E(x)=∑n≥1xn/(n⋅n!)E(x) = \sum_{n \ge 1} x^n/(n \cdot n!). The sum over k≥3k \ge 3 is then an integral of GG against a theta function. Splitting the integral at u0=4−au_0 = 4^{-a} and applying the transformation of θ4\theta_4 on (0,u0](0, u_0] gives, for every u0>0u_0 > 0,

log⁡Klog⁡2=log⁡22+Li⁡2(−12)+π212+12(∑k≥3(−1)kIk+∑m≥0Jm+M)\log K \log 2 = \log^2 2 + \operatorname{Li}_2(-\tfrac12) + \frac{\pi^2}{12} + \frac12\Bigl(\sum_{k \ge 3} (-1)^k I_k + \sum_{m \ge 0} J_m + M\Bigr)

with

Ik=∫u0∞e−k2uG(u) du,Jm=π∫0u0u−1/2e−π2(m+1/2)2/uG(u) du,M=∫0u0(e−u−e−4u−12)G(u) du.I_k = \int_{u_0}^\infty e^{-k^2 u} G(u)\,du, \quad J_m = \sqrt\pi \int_0^{u_0} u^{-1/2} e^{-\pi^2(m+1/2)^2/u} G(u)\,du, \quad M = \int_0^{u_0} \bigl(e^{-u} - e^{-4u} - \tfrac12\bigr) G(u)\,du.

For pp bits, about plog⁡2/u0\sqrt{p \log 2/u_0} terms IkI_k and pu0log⁡2/π\sqrt{p u_0 \log 2}/\pi terms JmJ_m are needed; the default u0=1/16u_0 = 1/16 balances their costs. Li⁡2(−12)\operatorname{Li}_2(-\tfrac12) comes from Li⁡2(1/9)\operatorname{Li}_2(1/9) and log⁡3\log 3 by Landen's identity, and MM is a rational series.

This is a generalization of the approximate functional equation of the Dirichlet LL-functions (Dirichlet L-functions), which is the same construction for the summand k−sk^{-s}: there the function GG is a power of uu, so that every term of the two series is a single incomplete gamma function. Here GG is an entire function, and the terms IkI_k and JmJ_m are themselves series, which can still be evaluated by binary splitting since their coefficients are rational.

The kk-terms. With K=k2K = k^2 and x=Ku0x = Ku_0, Ik=e−x∑n≥1(4/K)nen(x)/n2I_k = e^{-x}\sum_{n \ge 1} (4/K)^n e_n(x)/n^2, ene_n the truncated exponential series. The terms satisfy a triangular 2×22 \times 2 recurrence with rational coefficients, summed by matrix binary splitting; the factors e−k2u0e^{-k^2 u_0} of consecutive kk are propagated by multiplications by e−(2k+1)u0e^{-(2k+1)u_0}. The tail after NN terms is bounded through the Poisson weights in e−xen(x)e^{-x}e_n(x).

The dual terms. Jm=π ν3/2(c)J_m = \sqrt\pi\,\nu_{3/2}(c) with c=π2(m+12)2c = \pi^2(m+\tfrac12)^2 and the moments νt(c)=∫0u0u−te−c/uE(4u) du\nu_t(c) = \int_0^{u_0} u^{-t} e^{-c/u} E(4u)\,du. Integration by parts relates νt+1\nu_{t+1} to νt\nu_t, to the similar moments YtY_t of e4ue^{4u} and CtC_t of 1, and to the boundary values at u0u_0, which carry the factor e−c/u0e^{-c/u_0}; and −d/dc-d/dc shifts tt by one. So ν3/2\nu_{3/2} is a holonomic function of cc of order four whose only finite singularity is c=0c = 0, and it is evaluated by the bit-burst algorithm: starting values at a 64-bit dyadic c0c_0 near cc, from a shift series in terms of Γ(12,c0/u0)\Gamma(\tfrac12, c_0/u_0) (by mp_real_gamma_upper_half_frac) and e−c0/u0e^{-c_0/u_0}, then Taylor steps to dyadic points with 64⋅4j64 \cdot 4^j fractional bits converging to cc. The parts of the shift series cancel by up to ec0/u0e^{c_0/u_0} individually but their weighted sums only by about e4c0e^{4\sqrt{c_0}}, so O(c0)O(\sqrt{c_0}) guard bits suffice. All Taylor remainders, the tails of the starting values and the final distance to cc are bounded rigorously through upper incomplete gamma functions; the bounds carry the factor e−c0/u0e^{-c_0/u_0}, so that the late stages are computed only to the significant bits of JmJ_m, which is of order e−c/u0e^{-c/u_0}.

Matrix binary splitting. The kk-terms, the dual terms (starting values and Taylor steps), MM and the continued fraction for Γ(12,y)\Gamma(\tfrac12, y) all use one internal engine (_mp_real_linrec_eval) for recurrences Xl+1=(AlXl+flBlv)/qlX_{l+1} = (A_l X_l + f_l B_l v)/q_l with sums S+=(SlAXl+flSlBv)/qlS \mathrel{+}= (S^A_l X_l + f_l S^B_l v)/q_l and a scalar geometric forcing fl+1=φlfl/qlf_{l+1} = \varphi_l f_l/q_l, given by integer leaf matrices. The range is cut into chunks whose exact products (integer matrices over a common denominator) have about half the working precision in bits. Within a chunk, binary splitting combines the two halves in one augmented product that shares the transforms of each entry among the products (fmpz_mat_mul_fft_small, since fmpz_mat_mul does not choose the transformed product for such small matrices) when the entries have at least about 1.2⋅1041.2 \cdot 10^4 bits and the inner dimension d+g+sd+g+s is at least 6; for the narrow products of the kk-terms, separate products were faster at all sizes measured. Each chunk's matrix is then applied to the state vector (X,fv)(X, f v): above the chunks there are only matrix-vector products. The state is kept scaled by the product of the denominators so far, which is divided out once at the end. For large entries the application is one truncated transformed product (fmpz_mat_mul_fft_small_trunc, which transforms each state entry once for all the rows and accumulates the rows in the transformed domain), each state entry converted to fixed point with its own exponent, so that it keeps its relative accuracy as in ball arithmetic; for small entries it is done in ball arithmetic.

Parallelism and memory. The terms are independent tasks. The dual terms are the most expensive and take about four times the memory of a kk-term, so they start first and at most maxdual of them run at once (by default half the threads, until the last chunk of kk-terms has started; then any thread may take one), while the other threads take chunks of consecutive kk-terms, starting each chunk with e−k2u0e^{-k^2 u_0} and e−(2k+1)u0e^{-(2k+1) u_0} as powers of a shared e−u0e^{-u_0} (about 3log⁡2k3 \log_2 k multiplications instead of two exponentials). The exact products of large chunks also fork onto idle threads. Each finished term is added to one fixed-point integer with an integer error count, so no term is kept and the result does not depend on the order in which the terms finish. The memory is then that of the running terms, linear in the precision times the number of threads, and dominated by the transforms of the shared-transform products, which fft_small limits to flint_fft_small_max_transformed_ring_size per product (blocking the products beyond). At 10610^6 digits, a dual term takes about 370 numbers of the working precision with all transforms resident and a kk-term about 90. The user can reduce memory in exchange for a slight increase in running time by decreasing flint_fft_small_max_transformed_ring_size.

Glaisher's constant#

The Glaisher-Kinkelin constant A=exp⁡(1/12−ζ′(−1))A = \exp(1/12 - \zeta'(-1)) is computed directly from this formula, with ζ′(−1)\zeta'(-1) from acb_dirichlet_zeta_jet (see Zeta functions, polylogarithms and L-functions). Up to a cutoff (_acb_dirichlet_l_jet_use_afe: 3.5⋅1053.5 \cdot 10^5 bits with one thread, about 8⋅1048 \cdot 10^4 bits with 8 threads), this uses Euler-Maclaurin summation directly at s=−1s = -1; the reflection formula is not used for −4<Re⁡(s)<0-4 < \operatorname{Re}(s) < 0, since the arithmetic of Euler-Maclaurin summation is cheaper at s=−1s = -1 than at s=2s = 2 (by a factor 1.3–1.7 for ζ′(−1)\zeta'(-1)).

Euler-Maclaurin summation needs O(p)O(p) terms and O(p)O(p) Bernoulli numbers at precision pp, which costs O~(p2)\tilde O(p^2) time and O(p2)O(p^2) bits of memory (several gigabytes at p=4⋅105p = 4 \cdot 10^5). Above the cutoff, acb_dirichlet_zeta_jet instead computes ζ(−1+x)\zeta(-1+x) to O(x2)O(x^2) with the approximate functional equation (acb_dirichlet_l_fmpq_afe_jet), a sum of O(p)O(\sqrt{p}) incomplete gamma function jets evaluated by binary splitting, in time O~(p1.5)\tilde O(p^{1.5}) and with O(p)O(p) memory.

The reciprocal Fibonacci constant#

∑n≥11/Fn\sum_{n \ge 1} 1/F_n is computed from Gosper's series [Gos1974], corrected in [Arn2012],

∑n=1∞1Fn=∑n=0∞(−1)n(n−1)/2(F4n+3+(−1)nF2n+2)F2n+1F2n+2L1L3⋯L2n+1,\sum_{n=1}^{\infty} \frac{1}{F_n} = \sum_{n=0}^{\infty} \frac{(-1)^{n(n-1)/2} (F_{4n+3} + (-1)^n F_{2n+2})}{F_{2n+1} F_{2n+2} L_1 L_3 \cdots L_{2n+1}},

where Ln=2Fn−1+FnL_n = 2F_{n-1} + F_n is a Lucas number. The truncation error after N≥1N \ge 1 terms is bounded by (1/ϕ)N2(1/\phi)^{N^2}, so N≈1.2pN \approx 1.2 \sqrt{p} terms give pp bits. The series is not hypergeometric, but factoring out the multiplicative recurrence for L1L3⋯L_1 L_3 \cdots turns it into a product of O(p)O(\sqrt{p}) matrices with O(p)O(\sqrt{p})-bit entries, which binary splitting evaluates in quasilinear time.

Caching#

Each arb_const_ function keeps a thread-local cached ball. A request at precision pp above the cached precision recomputes the constant at p+32p + 32 bits; later requests at precision at most pp only round the cached value, to nearest with a radius of half a unit in the last place plus the cached error. π\pi and log⁡2\log 2 up to about 4000 bits are read from the static floors of π/4\pi/4 and log⁡2\log 2 (64 limbs on 64-bit machines), and γ\gamma up to 3456 bits from a static table, correctly rounded to nearest with a radius of half a unit in the last place. The caches are freed by flint_cleanup.

Inside mp_real the constants π/4\pi/4, log⁡2\log 2, 2/π2/\pi and 1/log⁡2−11/\log 2 - 1 (the last two derived from the first two) are needed over and over by the argument reductions, at precisions that grow during a computation. They are kept as exact floors, which have the property that makes a single cache entry serve every precision.

Lemma 4. For c≥0c \ge 0 and n≤Nn \le N, ⌊cBn⌋=⌊⌊cBN⌋/BN−n⌋\lfloor cB^n \rfloor = \lfloor \lfloor cB^N \rfloor / B^{N-n} \rfloor. That is, the floor at nn limbs is the top part of the floor at NN limbs.

Proof. For any real yy and integer q≥1q \ge 1, ⌊⌊y⌋/q⌋=⌊y/q⌋\lfloor \lfloor y \rfloor / q \rfloor = \lfloor y/q \rfloor; take y=cBNy = cB^N and q=BN−nq = B^{N-n}.

So a request at nn limbs reads the top limbs of the cached entry, and its result does not depend on the precision at which the entry was computed. A floor is obtained from a ball at a few guard limbs, retried with more guard limbs if the ball contains a multiple of B−nB^{-n}; for an irrational constant this terminates. When a request exceeds the cached precision NN, the entry is recomputed at max⁡(n+5,1.5N)\max(n + 5, 1.5N) limbs, so that a sequence of growing requests costs at most a constant factor more than its last one. The entry is a process-wide shared cache (thread_support.h): one version at a time, replaced under a lock and published with a release store, so readers never wait.

Use in FLINT#

The complex versions in acb (for example acb_const_pi) call these functions, and arb_hypgeom_gamma_fmpq uses Γ(1/3)\Gamma(1/3) and Γ(1/4)\Gamma(1/4) (the gamma function at rational arguments). The argument reductions of the elementary functions read π/4\pi/4, 2/π2/\pi, log⁡2\log 2 and 1/log⁡2−11/\log 2 - 1 from the cache of floors (static tables up to 64 limbs), and the AGM logarithm π/4\pi/4 and log⁡2\log 2. _mp_real_const_khinchin_afe implements the approximate functional equation for Khinchin's constant, with mp_real_gamma_upper_half_frac for its starting values.

The tutorial Computing π and other constants computes π\pi and other constants to many digits in complete programs.

Referenced from#

References#

Cite this page

The FLINT team, “Mathematical constants,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/special-functions/constants.html (generated 2026-11-20).