API Reference
The functions documented in this reference are in generate.h, unless otherwise stated.
It will be helpful to review the main Example for an overview of the interface.
Defining A Target Distribution
To generate random variates, librvg requires a specification of the target as a cumulative distribution function (CDF), a survival function (SF), or both. Functions that compute a CDF or SF must adhere to the following type.
-
typedef float (*cdf32_t)(double x);
A function type that takes as input a double x and returns a float.
- Use for a Cumulative Distribution Function
When used as a CDF, the function returns a float representing \(\Pr(X \le x)\) for the generated random variate \(X\). To be a valid specification, F must satisfy the following properties:
For all floats x, F(x) is a float in the unit interval [0, 1].
F(x) = 1, whenever x is NaN (i.e., if x != x).
F is nondecreasing, i.e., if x’ < x then F(x’) <= F(x).
- Use for a Survival Function
When used as a SF, the function returns a float representing \(\Pr(X > x)\) for the generated random variate \(X\). To be a valid specification, S must satisfy the following properties:
For all floats x, S(x) is a float in the unit interval [0, 1].
S(x) = 0, whenever x is NaN (i.e., if x != x).
S is nonincreasing, i.e., if x’ < x then S(x) <= S(x’).
Note
According to the above specification, probability distributions are permitted to include atoms at special floating-point values
-INFINITY,INFINITY, andNAN. Using a CDF F, this behavior can be achieved as follows.Atom at
-INFINITY: letF(-INFINITY) > 0.Atom at
INFINITY: letF(nextafterf(INFINITY, 0)) < F(INFINITY).Atom at
NAN: letF(INFINITY) < 1.
It is also possible to specify separate atoms at the negative and positive zeros (
0+,0-) of floating-point.
Accurate Sampling in the Right Tail
An advanced feature of librvg is the notion of a “dual distribution function” (DDF), which enables extended accuracy sampling in the upper tail of a distribution.
Recall that floating-point probabilities are dense near 0 but sparse
near 1. For example, a 32-bit CDF with F(x) < 1 has F(x) <= 1 - 2^-24, so it cannot
represent an upper-tail probability Pr(X > x) that lies strictly between 0
and 2^-24. A DDF solves this limitation. It can be built in two ways, and
both give full floating-point precision in the upper tail:
From a CDF and an SF, using
MAKE_DDF(). The result is also precise in the lower tail, as the CDF is used up to its median and the SF above it.From an SF alone, using
MAKE_DDF_SF(). The lower half of the distribution is then only as precise as1 - S(x), i.e., probabilities at most 1/2 are multiples of2^-24.
A CDF alone is already precise in the lower tail, and can be used directly
with the generators that do not have an _ext suffix. This
representation is further described in the Guarantees and
in [Saad and Lee, 2025, §6].
The type of a DDF is given in as follows.
-
typedef void (*ddf32_t)(double x, bool *b, float *p);
This function takes as input a double
x, and writes the result of evaluating a DDF atxto the pointersbandp. The interpretation ofbandpare as follows:If
bis set to 0, then \(\Pr(X \le x) = p\)If
bis set to 1, then \(\Pr(X \le x) = 1 - p\)
As with a CDF, a DDF must satisfy \(\Pr(X \le x) = 1\) whenever
xis NaN (i.e., ifx != x). That is, it must setbto 1 andpto 0. A DDF made usingMAKE_DDF()from a CDF and SF, or usingMAKE_DDF_SF()from an SF, that satisfy the above properties has this behavior automatically.
Functions that operate using a DDF have an _ext suffix (meaning “extended”).
Using GSL Distributions
librvg can interporate with existing CDF or SF implementations from the
GNU Scientific Library.
The following examples show how to wrap a Normal(0,1) and Poisson(5)
distributions to create new functions that are compatible with
with cdf32_t and ddf32_t.
// Gaussian distribution from the GNU library (continuous).
MAKE_CDF_P(gaussian_cdf, gsl_cdf_gaussian_P, 1);
MAKE_CDF_Q(gaussian_sf, gsl_cdf_gaussian_Q, 1);
MAKE_DDF(gaussian_ddf, gaussian_cdf, gaussian_sf);
// EXAMPLE 2: Poisson distribution from the GNU library (discrete).
MAKE_CDF_UINT_P(poisson_cdf, gsl_cdf_poisson_P, 5);
MAKE_CDF_UINT_Q(poisson_sf, gsl_cdf_poisson_Q, 5);
MAKE_DDF(poisson_ddf, poisson_cdf, poisson_sf);
The following macros are available, where
name should be a fresh C identifier (not a string)
for the name of the new function created from func. The suffixes
_P and _Q correspond to a CDF and SF, respectively, a naming
convention inherited from the GSL. The ... varargs are passed
directly to func. The MAKE_DDF() macro is not specific to a
CDF or SF created from the GSL, it can be used for any such pairing. The
MAKE_DDF_SF() macro creates a DDF from an SF alone, for a target that
is specified only by its survival function.
-
MAKE_CDF_P(name, func, ...)
Make a cumulative distribution over doubles from the GSL.
-
MAKE_CDF_Q(name, func, ...)
Make a survival distribution over doubles from the GSL.
-
MAKE_CDF_UINT_P(name, func, ...)
Make a cumulative distribution over unsigned integers from the GSL.
-
MAKE_CDF_UINT_Q(name, func, ...)
Make a survival distribution over unsigned integers from the GSL.
-
MAKE_DDF(name, func_cdf, func_sf)
Make a dual distribution function from a CDF and SF.
-
MAKE_DDF_SF(name, func_sf)
Make a dual distribution function from only a SF.
-
float cdf_discrete(double x, const float *P, size_t K);
Available in discrete.h.
A cumulative distribution function (
cdf32_t) for arbitrary discrete distributions over nonnegative integers. It is parameterized by a length-Kinput arrayPof cumulative probabilities, whereP[i]is the cumulative probability of integeri.
Generating Random Variates
Entropy-Optimal Generation
The generators are the entropy-optimal algorithms from [Saad and Lee, 2025].
They take as input the target cdf as described in the
previous section as well as a
prng, which is described in Pseudorandom Number Generators.
-
double generate_opt(cdf32_t cdf, struct flip_state *prng)
Generate random variables optimally from
cdf.
-
double generate_opt_ext(ddf32_t ddf, struct flip_state *prng)
Generate random variables optimally from
ddf.
Conditional-Bit Generation
librvg also includes implementations of the Conditional Bit Sampling (CBS)
method. These algorithms are described in Sobolewski and Payne [1972, Section II].
The performance of these functions is generally inferior to that of
generate_opt() and generate_opt_ext() in terms
of entropy consumption and runtime, as they use arbitrary precision
arithmetic via the GNU MP Bignum Library (libgmp).
-
double generate_cbs(cdf32_t cdf, struct flip_state *prng)
Generate random variables from
cdfusing Conditional Bit Sampling.
-
double generate_cbs_ext(ddf32_t ddf, struct flip_state *prng)
Generate random variables from
ddfusing Conditional Bit Sampling.
Inverse-Transform Method
librvg also includes exact generators based on the
inversion method.
These functions draw a uniform random number in the unit interval, rounded
to a float q, and return the exact q-quantile of the
target, as computed by quantile() and quantile_ext() (see
Querying a CDF). The generate_inversion_ext() function draws
q in a dual representation, to retain precision near 1.
-
double generate_inversion(cdf32_t cdf, struct flip_state *prng)
Generate random variables from
cdfusing the inversion method.
-
double generate_inversion_ext(ddf32_t ddf, struct flip_state *prng)
Generate random variables from
ddfusing the inversion method.
Querying a CDF
-
double quantile(cdf32_t cdf, float q)
-
double quantile_ext(ddf32_t ddf, bool d, float q)
These functions are used to compute the exact quantiles of a CDF or DDF. Recall that the quantile \(Q\) of a cumulative distribution function \(F\) is its generalized inverse:
\[\begin{aligned} Q(u) = \inf\{ x \in \mathbb{R} \mid u \le F(x) \} && (u \in [0,1]). \end{aligned}\]For a numerical function \(\texttt{cdf}: \mathbb{F} \to \mathbb{F} \cap [0,1]\), the exact quantile is
\[\begin{aligned} \texttt{quantile}(u) = \min\{ f \in \mathbb{F} \mid f \le \texttt{cdf}(x) \} && (u \in \mathbb{F} \cap [0,1]). \end{aligned}\]
Uniform Generation
Available in uniform.h
Generating Floats
These functions generate a uniform number in the unit interval [0,1],
according to the following process:
\[\begin{split}\begin{aligned} U' &\sim \mathrm{Uniform}_{\mathbb{R}}(0,1) \\ U &\gets \mathrm{round}_{\mathbb{F}, \alpha}(U') \end{aligned}\end{split}\]
where the variable \(U'\) is an infinitely precise uniform real and \(\mathrm{round}_{\mathbb{F}, \alpha}\) is a rounding function that converts a real number in \(\mathbb{R}\) to a floating-point number in \(\mathbb{F}\), according to a rounding mode \(\alpha\) (round up, round down, round to nearest).
-
enum round_mode
IEEE 754 Floating-Point Arithmetic Rounding Modes
Values:
-
enumerator RND_U
Round Up.
-
enumerator RND_D
Round Down.
-
enumerator RND_N
Round Nearest.
-
enumerator RND_U
-
float uniformf(enum round_mode mode, struct flip_state *prng)
Sample a uniform float in [0,1] with the given rounding mode.
-
double uniform(enum round_mode mode, struct flip_state *prng)
Sample a uniform double in [0,1] with the given rounding mode.
Generating Dual Floats
When performing inversion sampling using generate_inversion_ext(), it
is necessary to use a dual representation of floats that mirrors the dual
distribution function representations (see Guarantees).
-
void uniformf_ext(bool *d, float *q, struct flip_state *prng)
-
void uniform_ext(bool *d, double *q, struct flip_state *prng)
These functions simulate a uniform real number in the dual distribution format. The algorithm is as follows
\[\begin{split}\begin{aligned} D &\sim \mathrm{Bernoulli}(1/2) \\ \alpha &\gets D = 0 \;\, ? \;\, \texttt{RND\_U} : \texttt{RND\_D} \\ U' &\sim \mathrm{Uniform}_{\mathbb{R}}(0,1/2) \\ U &\gets \mathrm{round}_{\mathbb{F}, \alpha}(U') \end{aligned}\end{split}\]The result of the sample is stored in
dandq. Hered=0means that the sample isqandd=1means that the sample is1 - qwhere the subtraction is in exact (real) arithmetic.
Pseudorandom Number Generators
Available in prng.h and flip.h
Flip States
The generators described above
take as input a pseudorandom number generator called prng, which
must be obtained using make_flip_state(). The usual pattern is to
make a flip state using a gsl_rng pointer from the
GNU Scientific Library,
as follows.
// Prepare the random number generator.
gsl_rng * rng = gsl_rng_alloc(gsl_rng_default);
struct flip_state prng = make_flip_state(rng);
-
struct flip_state
A struct that maintains the state of a sequence of flips.
-
struct flip_state make_flip_state(gsl_rng *rng)
Initialize a
flip_stateusing anrng.
Random bits are obtained from a flip_state using the following
functions.
-
unsigned char flip(struct flip_state *s)
Generate a single bit from a
flip_state.
-
unsigned long long flip_k(struct flip_state *s, int k)
Generate a random
k-bit number from aflip_state.
-
unsigned long long randint(struct flip_state *s, int k)
Generate a random
k-bit number from aflip_state.
Additional PRNGs
There are a large number of pseudorandom number generators in the GSL, which can be used out of the box. librvg also provides two additional PRNG types.
-
extern const gsl_rng_type *gsl_rng_urandom
This generator draws system-level entropy using the getrandom syscall, which is typically
/dev/urandom. It maintains no state itself and cannot be seeded by the user, so calls such asgsl_rng_sethave no effect. Used primarily for workflows that require cryptographically secure random bits, see [Federal Office for Information Security, 2023] for a detailed description of the system entropy source.
-
extern const gsl_rng_type *gsl_rng_deterministic
This generator deterministically returns its seed. Its state consists of a single
unsigned long intvalue (typically 32 bits) which is always returned. It is useful for debugging and characterizing the properties of generators.