Random distributions with output fixed by the core, not by the standard library. More...

#include "math.hpp"
#include "rng.hpp"
#include <algorithm>
#include <cmath>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <numeric>
#include <ranges>
#include <span>
#include <stdexcept>
#include <utility>
#include <vector>

Classes
class	dasmig::core::discrete
	Index chosen with probability proportional to a weight. More...

Functions
constexpr std::uint64_t	dasmig::core::bounded (rng &r, std::uint64_t n)
	Uniform integer in [0, n).

template<std::integral T> requires (!std::same_as<T, bool>)
constexpr T	dasmig::core::uniform_int (rng &r, T lo, T hi)
	Uniform integer in [lo, hi], for any integral type except bool.

constexpr double	dasmig::core::uniform01 (rng &r) noexcept
	Uniform double in [0, 1).

double	dasmig::core::uniform_real (rng &r, double lo, double hi)
	Uniform double in [lo, hi).

bool	dasmig::core::bernoulli (rng &r, double p)
	True with probability `p`.

double	dasmig::core::normal (rng &r, double mean, double sd)
	Normally distributed double.

double	dasmig::core::lognormal (rng &r, double mu, double sigma)
	Log-normally distributed double.

template<std::ranges::random_access_range R> requires std::ranges::sized_range<R> && std::permutable<std::ranges::iterator_t<R>>
constexpr void	dasmig::core::shuffle (rng &r, R &&range)
	Shuffle a random-access range in place.

std::vector< std::size_t >	dasmig::core::sample_indices (rng &r, std::size_t n, std::size_t k)
	Choose k distinct indices from [0, n), in random order.

template<std::ranges::random_access_range R> requires std::ranges::sized_range<R>
constexpr decltype(auto)	dasmig::core::pick (rng &r, R &range)
	A uniformly chosen element of a non-empty range.

Detailed Description

Random distributions with output fixed by the core, not by the standard library.

Author: Diego Dasso Migotto (diegomigotto at hotmail dot com)

std::uniform_int_distribution, std::normal_distribution, std::discrete_distribution and std::shuffle use different algorithms in libc++, libstdc++ and the MSVC STL, so the same seed gives different results on different platforms. Every algorithm here is specified exactly (see each function) and is part of the core's output contract.

Each function consumes a fixed number of engine values for given arguments, except where rejection sampling is documented.

Definition in file distributions.hpp.

Function Documentation

◆ bernoulli()

bool dasmig::core::bernoulli	(	rng &	r,
		double	p
	)

inline

True with probability p.

uniform01(r) < p. Consumes one value, also for p = 0 and p = 1.

Parameters

r	Engine.
p	Probability of true.

Returns: The outcome.

Exceptions

std::invalid_argument If p is not in [0, 1].

Definition at line 190 of file distributions.hpp.

◆ bounded()

constexpr std::uint64_t dasmig::core::bounded	(	rng &	r,
		std::uint64_t	n
	)

constexpr

Uniform integer in [0, n).

Lemire's multiply-and-reject method (2019): the result is the high 64 bits of r() * n, redrawn while the low 64 bits are below 2^64 mod n. Unbiased; consumes one value, rarely more.

Parameters

r	Engine.
n	Exclusive upper bound.

Returns: A value in [0, n).

Exceptions

std::invalid_argument If n is 0.

Definition at line 78 of file distributions.hpp.

◆ lognormal()

double dasmig::core::lognormal	(	rng &	r,
		double	mu,
		double	sigma
	)

inline

Log-normally distributed double.

math::exp(normal(r, mu, sigma)).

Parameters

r	Engine.
mu	Mean of the underlying normal.
sigma	Standard deviation of the underlying normal.

Returns: The variate (positive).

Exceptions

std::invalid_argument As normal().

Definition at line 241 of file distributions.hpp.

◆ normal()

double dasmig::core::normal	(	rng &	r,
		double	mean,
		double	sd
	)

inline

Normally distributed double.

Marsaglia's polar method: draw u and v as 2 * uniform01(r) - 1 until s = u*u + v*v is in (0, 1), then return mean + sd * (u * sqrt((-2 * log(s)) / s)), with math::log. The second variate (from v) is discarded so no state is kept between calls. Consumes 2 values per attempt (on average 2.55 values).

Parameters

r	Engine.
mean	Mean.
sd	Standard deviation (0 returns `mean`).

Returns: The variate.

Exceptions

std::invalid_argument If mean or sd is not finite, or sd is negative.

Definition at line 213 of file distributions.hpp.

◆ pick()

template<std::ranges::random_access_range R>
requires std::ranges::sized_range<R>

constexpr decltype(auto) dasmig::core::pick	(	rng &	r,
		R &	range
	)

constexpr

A uniformly chosen element of a non-empty range.

range[bounded(r, size)]. Consumes one value (rarely more).

Parameters

r	Engine.
range	Non-empty random-access range (an lvalue: the result refers into it).

Returns: A reference to the chosen element.

Exceptions

std::invalid_argument If range is empty.

Definition at line 396 of file distributions.hpp.

◆ sample_indices()

std::vector< std::size_t > dasmig::core::sample_indices	(	rng &	r,
		std::size_t	n,
		std::size_t	k
	)

inline

Choose k distinct indices from [0, n), in random order.

Partial Fisher-Yates from the front: start from 0..n-1 and for i = 0 to k-1 swap element i with element i + bounded(r, n - i); return the first k. Consumes k values (rarely more). Allocates n indices.

Parameters

r	Engine.
n	Population size.
k	Sample size.

Returns: k distinct indices.

Exceptions

std::invalid_argument If k > n.

Definition at line 362 of file distributions.hpp.

◆ shuffle()

template<std::ranges::random_access_range R>
requires std::ranges::sized_range<R> && std::permutable<std::ranges::iterator_t<R>>

constexpr void dasmig::core::shuffle	(	rng &	r,
		R &&	range
	)

constexpr

Shuffle a random-access range in place.

Fisher-Yates from the end: for i = n-1 down to 1, swap element i with element bounded(r, i + 1). Consumes n - 1 values (rarely more).

Parameters

r	Engine.
range	Range to shuffle.

Definition at line 339 of file distributions.hpp.

◆ uniform01()

constexpr double dasmig::core::uniform01 ( rng & r )

constexprnoexcept

Uniform double in [0, 1).

The top 53 bits of one engine value, times 2^-53. Exact.

Parameters

r Engine.

Returns: A multiple of 2^-53 in [0, 1).

Definition at line 131 of file distributions.hpp.

◆ uniform_int()

template<std::integral T>
requires (!std::same_as<T, bool>)

constexpr T dasmig::core::uniform_int	(	rng &	r,
		T	lo,
		T	hi
	)

constexpr

Uniform integer in [lo, hi], for any integral type except bool.

lo + bounded(r, hi - lo + 1) computed in 64-bit unsigned arithmetic; the full 64-bit range takes one raw engine value.

Template Parameters

T	Integral type.

Parameters

r	Engine.
lo	Inclusive lower bound.
hi	Inclusive upper bound.

Returns: A value in [lo, hi].

Exceptions

std::invalid_argument If lo > hi.

Definition at line 111 of file distributions.hpp.

◆ uniform_real()

double dasmig::core::uniform_real	(	rng &	r,
		double	lo,
		double	hi
	)

inline

Uniform double in [lo, hi).

lo + (hi - lo) * uniform01(r), replaced by the largest double below hi if rounding reaches hi. Returns lo when lo == hi. Consumes one value.

Parameters

r	Engine.
lo	Inclusive lower bound.
hi	Exclusive upper bound.

Returns: A value in [lo, hi), or lo when lo == hi.

Exceptions

std::invalid_argument If a bound is not finite, lo > hi, or hi - lo overflows.

Definition at line 168 of file distributions.hpp.

Classes

Functions

Detailed Description

Function Documentation

◆ bernoulli()

◆ bounded()

◆ lognormal()

◆ normal()

◆ pick()

◆ sample_indices()

◆ shuffle()

◆ uniform01()

◆ uniform_int()

◆ uniform_real()