log.h
[view source]

Contains useful functions for performing arithmetic in log space, such as computing the maximum of an array, computing sum-exp, log-sum-exp, and normalization. This file also contains log_cache, which caches the logarithms of positive integers. All functions in this file avoid loss of precision by performing operations in log space when feasible.

In the following example, the array { -100.0, -100.0, -100.0 + log(2.0), -100.0 + log(4.0) } of log probabilities is normalized and printed. The expected output is [0.125000, 0.125000, 0.250000, 0.500000].

#include <math/log.h>
#include <core/io.h>
using namespace core;

int main() {
    double a[] = { -100.0, -100.0, -100.0 + log(2.0), -100.0 + log(4.0) };
    normalize_exp(a, 4);
    print(a, 4, stdout);
}

Classes, functions, and variables in this file
#defineLOG_ZERO
floatlog_probability (float src)
doublelog_probability (double src)
voidmax (V & max, const T * src, unsigned int length, unsigned int skip)
voidmax (V & max, const T * src, const P * prior, unsigned int length, unsigned int skip)
Vmax (const T * src, unsigned int length, unsigned int skip)
Vmax (const T * src, const P * prior, unsigned int length, unsigned int skip)
Vmax (const Collection & src)
Vmax (const T * src, unsigned int length)
Vsumexp (const T * src, unsigned int length, unsigned int skip, const V & shift)
Vsumexp (const T * src, const P * prior, unsigned int length, unsigned int skip, const V & shift)
Vsumexp (const Collection & src, const V & shift)
voidnormalize (const T * src, V * dst, unsigned int length, unsigned int skip, const V & normalization)
voidnormalize_exp (const T * src, V * dst, unsigned int length, unsigned int skip, const V & normalization)
voidnormalize_exp (const T * src, const P * prior, V * dst, unsigned int length, unsigned int skip, const V & normalization)
Vlogsumexp (const T * src, unsigned int length, unsigned int skip = 1)
Vlogsumexp (const T * src, const P * prior, unsigned int length, unsigned int skip = 1)
Vlogsumexp (const Collection & src)
voidnormalize (const T * src, V * dst, unsigned int length, unsigned int skip = 1)
voidnormalize_exp (const T * src, V * dst, unsigned int length, unsigned int skip = 1)
voidnormalize_exp (const T * src, const P * prior, V * dst, unsigned int length, unsigned int skip = 1)
voidnormalize_exp (T * x, unsigned int length)
Vlogsumexp (const V & first, const V & second)
Vlogdiffexp (const V & first, const V & second)
structlog_cache
[view source]
#define LOG_ZERO -1.0e16

This value is used for log(0) in some operations to avoid floating-point infinities and improve performance.

[view source]
float log_probability(
floatsrc)

Returns src. This function is defined so that the function in this file max, sum_exp, and normalize behave correctly when T is float.

[view source]
double log_probability(
doublesrc)

Returns src. This function is defined so that the function in this file max, sum_exp, and normalize behave correctly when T is double.

[view source]
template<typename T, typename V>
void max(
V &max,
const T *src,
unsigned intlength,
unsigned intskip)
Computes the maximum log probability of the elements in src with the given length, only inspecting the elements at every skip locations, until length elements have been considered. For example, if skip = 2, this function will find the maximum of the elements at every even index. The computed maximum is stored in max.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename P, typename V>
void max(
V &max,
const T *src,
const P *prior,
unsigned intlength,
unsigned intskip)

Computes the maximum sum of the log probability of the elements in src and the elements in prior with the given length, only inspecting the elements in src at every skip locations, until length elements have been considered. For example, if skip = 2, this function will find the maximum of the elements at every even index. Note that skip does not affect the inspection of elements in prior. The computed maximum is stored in max.

So more precisely, this function computes:

\[ max_i \{ f(\text{src}[i \cdot \text{skip}]) + g(\text{prior}[i]) \}. \]
where $ f(\cdot) $ is the function V log_probability(const T&) and $ g(\cdot) $ is the function V log_probability(const P&).

T

the type of every element in src, for which the function V log_probability(const T&) is defined.

P

the type of every element in prior, for which the function V log_probability(const P&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename V = typename >
V max(
const T *src,
unsigned intlength,
unsigned intskip)
Returns the maximum log probability of the elements in src with the given length, only inspecting the elements at every skip locations, until length elements have been considered. For example, if skip = 2, this function will find the maximum of the elements at every even index.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities. By default, if T is a floating-point type, V is the same type.

[view source]
template<typename T, typename P, typename V = typename >
V max(
const T *src,
const P *prior,
unsigned intlength,
unsigned intskip)

Returns the maximum sum of the log probability of the elements in src and the elements in prior with the given length, only inspecting the elements in src at every skip locations, until length elements have been considered. For example, if skip = 2, this function will find the maximum of the elements at every even index. Note that skip does not affect the inspection of elements in prior. The computed maximum is stored in max.

So more precisely, this function computes:

\[ max_i \{ f(\text{src}[i \cdot \text{skip}]) + g(\text{prior}[i]) \}. \]
where $ f(\cdot) $ is the function V log_probability(const T&) and $ g(\cdot) $ is the function V log_probability(const P&).

T

the type of every element in src, for which the function V log_probability(const T&) is defined.

P

the type of every element in prior, for which the function V log_probability(const P&) is defined.

V

the type of the log probabilities. By default, if T is a floating-point type, V is the same type.

[view source]
template<typename Collection, typename V = typename >
V max(
const Collection &src)
Returns the maximum log probability of the elements in the collection src.
Collection

the type of a collection of items, each of type T, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename V = typename >
V max(
const T *src,
unsigned intlength)
Returns the maximum log probability of the given native array src.
T

the type of every element in src, for which the function V log_probability(const T&) is defined, where V is the return type of this function.

[view source]
template<typename T, typename V>
V sumexp(
const T *src,
unsigned intlength,
unsigned intskip,
const V &shift)
This function returns
\[ \sum_{i=0}^{\text{length}-1} \exp\{ f(\text{src}[i * \text{skip}]) - \text{shift} \} \]
where $ f(\cdot) $ is the function V log_probability(const T&).
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename P, typename V>
V sumexp(
const T *src,
const P *prior,
unsigned intlength,
unsigned intskip,
const V &shift)
This function returns
\[ \sum_{i=0}^{\text{length}-1} \exp\{ f(\text{src}[i * \text{skip}]) + g(\text{prior}[i]) - \text{shift} \} \]
where $ f(\cdot) $ is the function V log_probability(const T&) and $ g(\cdot) $ is the function V log_probability(const P&).
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

P

the type of every element in prior, for which the function V log_probability(const P&) is defined.

V

the type of the log probabilities.

[view source]
template<typename Collection, typename V>
V sumexp(
const Collection &src,
const V &shift)
This function returns
\[ \sum_{c\in\text{src}} \exp\{ f(c) - \text{shift} \} \]
where $ f(\cdot) $ is the function V log_probability(const T&).
Collection

the type of a collection of items, each of type T, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename V>
void normalize(
const T *src,
V *dst,
unsigned intlength,
unsigned intskip,
const V &normalization)
Copies the log probabilities from src into dst, subtracting normalization from each element. This function assumes dst is initialized and has sufficient capacity. This function only considers elements at every skip positions, until length elements have been considered. For example, if skip = 2, only the elements at even indices are copied. Note that src and dst can be the same.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename V>
void normalize_exp(
const T *src,
V *dst,
unsigned intlength,
unsigned intskip,
const V &normalization)
Copies the log probabilities from src into dst, subtracting normalization from each element, and taking the natural exponent of the result. This function assumes dst is initialized and has sufficient capacity. This function only considers elements at every skip positions, until length elements have been considered. For example, if skip = 2, only the elements at even indices are copied. Note that src and dst can be the same.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename P, typename V>
void normalize_exp(
const T *src,
const P *prior,
V *dst,
unsigned intlength,
unsigned intskip,
const V &normalization)
This function computes
\[ \exp\{ f(\text{src}[i * \text{skip}]) + g(\text{prior}[i]) - \text{normalization} \} \]
and stores the result in dst[i], where i ranges from 0 to length - 1, and $ f(\cdot) $ is the function V log_probability(const T&) and $ g(\cdot) $ is the function V log_probability(const P&). Note that src and dst can be the same.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

P

the type of every element in prior, for which the function V log_probability(const P&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename V = typename >
V logsumexp(
const T *src,
unsigned intlength,
unsigned intskip = 1)
Returns the natural logarithm of the sum of the natural exponent of the elements in src, skipping every skip elements, until length elements have been considered.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename P, typename V = typename >
V logsumexp(
const T *src,
const P *prior,
unsigned intlength,
unsigned intskip = 1)
Returns the natural logarithm of the sum of the natural exponent of the elements in src, with the given prior, skipping every skip elements, until length elements have been considered. Note that skip does not affect the inspection of the elements in prior.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

P

the type of every element in prior, for which the function V log_probability(const P&) is defined.

V

the type of the log probabilities.

[view source]
template<typename Collection, typename V = typename >
V logsumexp(
const Collection &src)
Returns the natural logarithm of the sum of the natural exponent of the elements in the collection src.
Collection

the type of a collection of items, each of type T, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename V>
void normalize(
const T *src,
V *dst,
unsigned intlength,
unsigned intskip = 1)
Computes the normalized log probabilities of the elements in src and stores them in dst, skipping every skip elements, until length elements have been considered. Note that src and dst can be the same.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename V>
void normalize_exp(
const T *src,
V *dst,
unsigned intlength,
unsigned intskip = 1)
Computes the normalized probabilities of the elements in src and stores them in dst, skipping every skip elements, until length elements have been considered. Note that src and dst can be the same.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T, typename P, typename V>
void normalize_exp(
const T *src,
const P *prior,
V *dst,
unsigned intlength,
unsigned intskip = 1)
Computes the normalized probabilities of the elements in src and stores them in dst, skipping every skip elements, until length elements have been considered. Note that skip does not affect the inspection of the elements in prior. Also note that src and dst can be the same.
T

the type of every element in src, for which the function V log_probability(const T&) is defined.

P

the type of every element in prior, for which the function V log_probability(const P&) is defined.

V

the type of the log probabilities.

[view source]
template<typename T>
void normalize_exp(
T *x,
unsigned intlength)

Normalizes the elements in src. Like all functions in this file, loss of precision is avoided by performing operations in log space when feasible.

[view source]
template<typename V>
V logsumexp(
const V &first,
const V &second)
Returns the natural logarithm of the sum of the natural exponents of first and second.
V

satisfies is_arithmetic.

[view source]
template<typename V>
V logdiffexp(
const V &first,
const V &second)
Returns the natural logarithm of exp(first) - exp(second).
V

satisfies is_arithmetic.

struct log_cache
[view source]

template<typename V>

This structure caches natural logarithms of positive integers.

The following example displays a typical use-case of this cache. The expected output is log(2) = 0.693147, log(183) = 5.209486, sum from i=1 to 999 of log(i) = 5905.220423.

#include <math/log.h>
using namespace core;

int main() {
    log_cache<double> cache(1000);
    printf("log(2) = %lf, ", cache.get(2));
    printf("log(183) = %lf, ", cache.get(183));

    double sum = 0.0;
    for (unsigned int i = 1; i < 1000; i++)
        sum += cache.get(i);
    printf("sum from i=1 to 999 of log(i) = %lf\n", sum);
}

V

satisfies is_arithmetic.

Public members
log_cache (unsigned int initial_size)
boolensure_size (unsigned int requested_size)
Vget (unsigned int x) const
static log_cache< V > &instance ()
[view source]
log_cache::log_cache(
unsigned intinitial_size)

Constructs the cache with the given initial_size. The natural logarithms up to and includig log(initial_size - 1) are precomputed and stored.

[view source]
bool log_cache::ensure_size(
unsigned intrequested_size)

Checks that the natural logarithms up to and including log(requested_size - 1) are computed and stored.

[view source]
V log_cache::get(
unsigned intx) const

Returns the natural logarithm of x. This function assumes that log(x) has already been computed, either by the constructor or by ensure_size, and no bounds checking is performed.

[view source]
static log_cache< V > & log_cache::instance()

Returns a static instance of a log_cache, with type V.