CKP

Pure Python implementations of competitive programming algorithms.

View the Project on GitHub 123jimin/ckp

Numeric Functions

ckp.numeric contains constants and functions for accurate numeric computations.

Convention

In this document, when a function foo’s signature is listed like this:

foo() -> float | fractions.Fractions | decimal.Decimal

then it means that there are different versions of foo available to use:

(Unfortunately, currently there’s no function that returns values other than float.)

Constants

CKP does not provide any global variables, neither does this package. Call the function and store the value to a global variable if you wish.

Functions

log_falling_factorial(n: int, k: int) -> float

Computes the log value of the falling factorial $(n)_k = n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}$.

Usually, math.lgamma(n+1) - math.lgamma(n-k+1) gives the desired answer, but when n is extremely large compared to k, that method would yield an incorrect result.

log_falling_factorial uses the following formula, based on Stirling’s approximation.

\[\log \Gamma(z) = z \log z - z - \frac{1}{2} \log z + \frac{1}{2} \log 2 \pi + \frac{1}{12 z} + O(\frac{1}{z^3})\]

log_comb(n: int, k: int) -> float

This function assumes that $0 \le k \le n$.

Computes $\log {n \choose k}$. Usually, math.lgamma(n+1) - math.lgamma(n-k+1) - math.lgamma(k+1) gives the desired answer, but when n is extremely large compared to k, that method would yield an incorrect result.

log_comb uses the same Stirling’s approximation log_falling_function does.

harmonic_number(n: int) -> float

Computes the n-th harmonic number $H_n = \sum_{i=1}^n \frac{1}{i}$ in constant time, using the following approximation.

\[H_n = \log n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \frac{1}{240n^8} + \cdots\]

Every harmonic numbers are rational numbers, but the exact version of this function (returning fractions.Fraction) is not planned to be implemented, as it’s practically useless.

coupon_collector_expected(n: int, k: int) -> float

Computes $n (H_n - H_{n-k})$, the expected number of coupons collected for collecting $k$ of $n$ coupons.

One may tempt to use n * (harmonic_number(n) - harmonic_number(n-k)) for this, but it’s not accurate enough for large $n$ and small $k$; $H_n$ and $H_{n-k}$ are very close to each other, so the subtraction may cause a significant loss of precision.

Instead, (let $r = n-k$) $H_n - H_r$ is computed like this:

\[\begin{aligned} H_n - H_{n-k} &\approx \log n - \log r + \left( \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} \right) - \left( \frac{1}{2r} - \frac{1}{12r^2} + \frac{1}{120r^4} \right) \\ &= \log \frac{n}{r} + \frac{60n^3 - 10n^2 + 1}{120n^4} - \frac{60r^3 - 10r^2 + 1}{120r^4} \end{aligned}\]

Note that math.log1p should be used to accurately compute $\log \frac{n}{r} = \log (1 + \frac{k}{r})$.