partitions.h – computation of the partition function¶
This module implements the asymptotically fast algorithm for evaluating the integer partition function \(p(n)\) described in [Joh2012]. The idea is to evaluate a truncation of the HardyRamanujanRademacher series using tight precision estimates, and symbolically factoring the occurring exponential sums.
An implementation based on floatingpoint arithmetic can also be found in FLINT. That version relies on some numerical subroutines that have not been proved correct.
The implementation provided here uses ball arithmetic throughout to guarantee a correct error bound for the numerical approximation of \(p(n)\). Optionally, hardware double arithmetic can be used for lowprecision terms. This gives a significant speedup for small (e.g. \(n < 10^6\)).

void
partitions_rademacher_bound
(arf_t b, const fmpz_t n, ulong N)¶ Sets \(b\) to an upper bound for
\[M(n,N) = \frac{44 \pi^2}{225 \sqrt 3} N^{1/2} + \frac{\pi \sqrt{2}}{75} \left( \frac{N}{n1} \right)^{1/2} \sinh\left(\frac{\pi}{N} \sqrt{\frac{2n}{3}}\right).\]This formula gives an upper bound for the truncation error in the HardyRamanujanRademacher formula when the series is taken up to the term \(t(n,N)\) inclusive.

void
partitions_hrr_sum_arb
(arb_t x, const fmpz_t n, slong N0, slong N, int use_doubles)¶ Evaluates the partial sum \(\sum_{k=N_0}^N t(n,k)\) of the HardyRamanujanRademacher series.
If use_doubles is nonzero, doubles and the system’s standard library math functions are used to evaluate the smallest terms. This significantly speeds up evaluation for small \(n\) (e.g. \(n < 10^6\)), and gives a small speed improvement for larger \(n\), but the result is not guaranteed to be correct. In practice, the error is estimated very conservatively, and unless the system’s standard library is broken, use of doubles can be considered safe. Setting use_doubles to zero gives a fully guaranteed bound.

void
partitions_fmpz_fmpz
(fmpz_t p, const fmpz_t n, int use_doubles)¶ Computes the partition function \(p(n)\) using the HardyRamanujanRademacher formula. This function computes a numerical ball containing \(p(n)\) and verifies that the ball contains a unique integer.
If n is sufficiently large and a number of threads greater than 1 has been selected with
flint_set_num_threads()
, the computation time will be reduced by using two threads.See
partitions_hrr_sum_arb()
for an explanation of the use_doubles option.

void
partitions_fmpz_ui
(fmpz_t p, ulong n)¶ Computes the partition function \(p(n)\) using the HardyRamanujanRademacher formula. This function computes a numerical ball containing \(p(n)\) and verifies that the ball contains a unique integer.

void
partitions_fmpz_ui_using_doubles
(fmpz_t p, ulong n)¶ Computes the partition function \(p(n)\), enabling the use of doubles internally. This significantly speeds up evaluation for small \(n\) (e.g. \(n < 10^6\)), but the error bounds are not certified (see remarks for
partitions_hrr_sum_arb()
).

void
partitions_leading_fmpz
(arb_t res, const fmpz_t n, slong prec)¶ Sets res to the leading term in the HardyRamanujan series for \(p(n)\) (without Rademacher’s correction of this term, which is vanishingly small when \(n\) is large), that is, \(\sqrt{12} (11/t) e^t / (24n1)\) where \(t = \pi \sqrt{24n1} / 6\).